Following on Joshua's comment, I remember being taught the following procedure. Take the greatest square below 2257; this is 47^2 = 2209. The residue after this square is removed is 48. Now we want to calculate N^2 - 2257 for successive N after 47. They are fairly easily generated: 48 + (47 + 48) = 145 145 + (48 + 49) = 242 242 + (49 + 50) = 341 341 + (50 + 51) = 442 442 + (51 + 52) = 545 545 + (52 + 53) = 650 We are looking for perfect squares in this sequence, and so far we haven't found one. But in fact we've now swept clean a fairly big area around 47. The square root of 650 is bigger than 25, so 2257 has no factors between 47 and 47-26 = 21. So after eliminating 7, 11, and 13 by the 1001-trick, the only primes left to check are 17 and 19. I find that checking divisibility is usually easier than actually dividing. You can add or subtract multiples of the candidate divisor freely, and you can also divide by primes that aren't equal to the candidate, without affecting divisibility. For 2257 and 17, my thought process goes from 2257 to 2240, to 224, to 112, to 56, ... which I can factor fast and doesn't have any 17's. For 19, it's even easier: 2257 to 2200, which again one can "see" all the factors of, and 19 isn't among them. So 2257 is prime. Without pencil and paper, I usually skip the square searching and progress straight to testing candidate divisors, which I somehow find easier to do in my head. On Fri, Dec 16, 2011 at 3:21 PM, Joshua Zucker <joshua.zucker@gmail.com>wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun