On 12/16/2011 3:03 PM, Dan Asimov 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?
Fermat's factorization method can be combined with trial division to make a practical technique for mental factorization of 4-digit numbers. You can find the details in this Wikipedia article, http://en.wikipedia.org/wiki/Fermat%27s_factorization_method, but the idea is that an odd composite N must be the difference of squares, and if the factors are relatively close, the larger square will not be much larger than N. In this case, the next square after 2257 is 48^2 = 2304, but since N is 1 mod 4, the difference cannot be a square. The next odd square is 49^2 = 2401 and the difference is 144 = 12^2. Thus 2257 = 49^2 - 12^2 = 37 61. By the way, you can test for divisibility by 7, 11 and 13 simultaneously by "casting out 1001s". In this case, 2257 - 2002 = 255 = 3 5 17, so none of them is a divisor. (If you get a less obvious three-digit remainder, say 481, you can multiply it by 10 or 100 and repeat: 48100 - 48048 = 52, so it's a multiple of 13.) -- Fred W. Helenius fredh@ix.netcom.com