On Fri, Dec 16, 2011 at 12:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Take a number like 2257 (say < 10000), easily checked to have no prime factors < 13.
To find the least prime factor of such a number N, is there on average a faster way (after having excluded primes < 13) than the naïve method of dividing it by each prime in order <= sqrt(N) until one divides N evenly?
Check the smaller primes by division, and at some point when you're close to sqrt(N) it gets easier to think about 2257 + a^2 = b^2, where you know that the values of a can't be so big. Squares are easier to compute, rather than dividing, and after a while you can learn all the squares < 10000 pretty well (or at least learn the ones up to 25, and then use things like (25+n)^2 = (25-n)^2 + 100n to get the rest). --Joshua Zucker