a better prime number generator
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.
"""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)
More information about the Python-list