a better prime number generator

John Thingstad john.thingstad at chello.no
Sun Oct 21 22:15:04 CEST 2001

> hi all,
> I have just been introduced to pyton and find it a very good ( takes
> off all the bookwork ) language. I was trying to develope a ast prime
> number generator. I designed the following algo. Can you please
> suggest a faster one or modifications to this only to make it faster
This should work fast up to say 10000. 
Beond that you will need to use Fermant's little theorem and Pomerance quadric sieve.
But that is to lengthy to discuss here.

def prime(n):
                """Simple prime generator using Aristophanes sieve."""
	set = range(2, n)
	for n in range (2, int(math.sqrt(n)), 2):
		set = [x for x in set if x== n or x % p != 0)
	return set

More information about the Python-list mailing list