John Whittington wrote in message
>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
>>if a number, N,
>>is prime, you only need to see if it is evenly divisible by any prime
>>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.