Date: Fri, 7 Jan 2000 22:00:43 GMT Lou Pogoda "SAS(r) Discussion" Lou Pogoda @Home Network Re: Testing if prime

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.

Back to: Top of message | Previous page | Main SAS-L page