Since no one has yet to show a true sieve or explain it, I will try.
The basic method is to start counting at 2 and eliminate 2*2 and all higher multiples of 2 (ie 4, 6, 8...) since none of them can be prime. 3 survived the first round so it is prime and now we eliminate 3*3 and all higher multiples of 3 (ie 9, 12, 15...). 4 was eliminated, 5 survived etc. The squaring of each prime is an optimization that makes use of the fact that all smaller multiples of each new prime will have been eliminated in previous rounds. Only the prime numbers will be left as you count and eliminate non-primes using this process.
Here is a very simple version, notice it does not use modulo division or roots:
def primes(n): # Sieve of Eratosthenes
prime, sieve = [], set()
for q in xrange(2, n+1):
if q not in sieve:
prime.append(q)
sieve.update(range(q*q, n+1, q))
return prime
>>> primes(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73
79, 83, 89, 97]
The simple approach above is surprisingly fast but does not make use of the fact that primes can be only odd numbers.
Here is a generator based version that is faster than any other I have found but hits a Python memory limit at n = 10**8 on my machine.
def pgen(n): # Fastest Eratosthenes generator
yield 2
sieve = set()
for q in xrange(3, n+1, 2):
if q not in sieve:
yield q
sieve.update(range(q*q, n+1, q+q))
>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10)
5.987867565927445
Here is a slightly slower but much more memory efficient generator version:
def pgen(maxnum): # Sieve of Eratosthenes generator
yield 2
np_f = {}
for q in xrange(3, maxnum+1, 2):
f = np_f.pop(q, None)
if f:
while f != np_f.setdefault(q+f, f):
q += f
else:
yield q
np = q*q
if np < maxnum:
np_f[np] = q+q
>>> timeit('n in pgen(n)', setup="from __main__ import pgen; n=10**6", number=10)
7.420101730225724
>>> list(pgen(10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
To test if a number is prime just do:
>>> 539 in pgen(539)
False
>>> 541 in pgen(541)
True
Here are some hints as to how this more memory efficient version works. It uses a dict
to store only the bare minimum of information, the next non-prime numbers (as keys) along with their factors (as values). As each non-prime is found in the dict
, it is removed and the next non-prime key is added with the same factor value.