Prime number testing

[Paul Miller]

pwmiller1 at adelphia.net (Paul Miller) wrote in message news:<2e363c08.0407110702.32564d69 at posting.google.com>...

> import math
> 
> def isPrime (x):
> 	if x % 2 == 0: 
> 		return 0
> 	limit = int(math.sqrt (x))
> 	for i in xrange (3,limit+1,2):
> 		if x % i == 0:
> 			return 0
> 	return 1
> 
> I know your function attempted to sieve out multiples of 3 as well,
> but that only improves performance in case x is composite.
> 
> Looking at this and assuming that 2**61 -1 is prime, you find that
> this will do (2**61-1) or about 2**60 divisions.  If you assume you
> can perform 10**9 divisions per sec, then this will take about 36
> years. That's why your function is slow.

This should of course be (2**61-1)/2 divisions. :P

> The catch is you need a lot of memory to store all
> those primes. ;) [417214937 gigabytes, or so, provided you don't
> introduce a compression scheme, which would slow you down a bit]

Coincidentally, BTW, this would be about the time Longhorn comes out,
and it's not far off the minimum spec for the OS, either.