John Whittington wrote: > > 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).

No, Dan's right. Think about it as a sequential effort starting with the number 2. If N is divisible by *a* number less than sqrt(N), then it must be divisible by the primes which make up that divisor, and they have to be even smaller than the number you just used as the divisor.

> 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!

Umm, 2. You forgot 2. 46 is 2*23.

And if you don't believe me [and who wouldnt :-] then let me recommend "Elementary Number Theory" by David Burton. It's an easy read for someone with your background.

David -- David Cassell, OAO cassell@mail.cor.epa.gov Senior Computing Specialist mathematical statistician