Hello mr Asimov, yes maybe : since 1001 is 7 * 11 * 13 then by just looking at the number we know if it is a multiple of 1001, ... but the number of course has to be a mutiple of 1001 which is somewhat rare. There are tricks for each prime up to 97 I believe but the application is too complicated to be made mentaly. The only shortcut I know is to use complements, for example with 19 , it is simpler to figure out a way to exclude a multiple of 19 if we consider that 19 = 20 - 1. The same for 11, 31, 41, 61, etc,. Carefuly applied this could lead to a simple trick to exclude a series of primes in one shot (sort of). just a thought, best regards, Simon Plouffe Le 16/12/2011 21:03, Dan Asimov a écrit :
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?
--Dan
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun