John Whittington wrote in message <3.0.1.32.20000107005841.0073d2ec@pop3.powernet.co.uk>... >At 00:05 07/01/00 GMT, Daniel J. Nordlund wrote: > >>The question was how to test a large set of numbers for primality(?), >>efficiently. The numbers can be as large as 9999999999 (ten digits). To >test >>if a number, N, >>is prime, you only need to see if it is evenly divisible by any prime number >>less than or equal to the SQRT(N). > >Dan, I keep seeing this assertion, but frankly don't get it. It is surely >the case that one has to test whether N is divisible by ALL NUMBERS ><=SQRT(N) - not all PRIME NUMBERS <=SQRT(N). > >For example, take 46. SQRT(46) = 6.78, so that the non-unity primes ><=SQRT(46) are 3 and 5. 46 certainly doesn't divide by either of those, >but it equally certainly is not prime! >

Not quite. The non-unity primes <= SQRT(46) are 2, 3, and 5. 46 certainly IS divisible by one of those, and 46 is certainly not prime.

So far, the rule (or "assertion" if you insist) holds.