Warning: timeit results may vary due to differences in hardware or version of Python.
Below is a script which compares a number of implementations:
- ambi_sieve_plain,
- rwh_primes,
- rwh_primes1,
- rwh_primes2,
- sieveOfAtkin,
- sieveOfEratosthenes,
- sundaram3,
- sieve_wheel_30,
- ambi_sieve [requires numpy]
- primesfrom3to [requires numpy]
- primesfrom2to [requires numpy]
Many thanks to stephan for bringing sieve_wheel_30 to my attention. Credit goes to Robert William Hanks for primesfrom2to, primesfrom3to, rwh_primes, rwh_primes1, and rwh_primes2.
Of the plain Python methods tested, with psyco, for n=1000000, rwh_primes1 was the fastest tested.
+---------------------+-------+
| Method | ms |
+---------------------+-------+
| rwh_primes1 | 43.0 |
| sieveOfAtkin | 46.4 |
| rwh_primes | 57.4 |
| sieve_wheel_30 | 63.0 |
| rwh_primes2 | 67.8 |
| sieveOfEratosthenes | 147.0 |
| ambi_sieve_plain | 152.0 |
| sundaram3 | 194.0 |
+---------------------+-------+
Of the plain Python methods tested, without psyco, for n=1000000, rwh_primes2 was the fastest.
+---------------------+-------+
| Method | ms |
+---------------------+-------+
| rwh_primes2 | 68.1 |
| rwh_primes1 | 93.7 |
| rwh_primes | 94.6 |
| sieve_wheel_30 | 97.4 |
| sieveOfEratosthenes | 178.0 |
| ambi_sieve_plain | 286.0 |
| sieveOfAtkin | 314.0 |
| sundaram3 | 416.0 |
+---------------------+-------+
Of all the methods tested, allowing numpy, for n=1000000, primesfrom2to was the fastest tested.
+---------------------+-------+
| Method | ms |
+---------------------+-------+
| primesfrom2to | 15.9 |
| primesfrom3to | 18.4 |
| ambi_sieve | 29.3 |
+---------------------+-------+
Timings were measured using the command:
python -mtimeit -s"import primes" "primes.{method}[1000000]"
with {method} replaced by each of the method names.
primes.py:
#!/usr/bin/env python
import psyco; psyco.full[]
from math import sqrt, ceil
import numpy as np
def rwh_primes[n]:
# //stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange[3,int[n**0.5]+1,2]:
if sieve[i]:
sieve[i*i::2*i]=[False]*[[n-i*i-1]/[2*i]+1]
return [2] + [i for i in xrange[3,n,2] if sieve[i]]
def rwh_primes1[n]:
# //stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * [n/2]
for i in xrange[3,int[n**0.5]+1,2]:
if sieve[i/2]:
sieve[i*i/2::i] = [False] * [[n-i*i-1]/[2*i]+1]
return [2] + [2*i+1 for i in xrange[1,n/2] if sieve[i]]
def rwh_primes2[n]:
# //stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a list of primes, 2 =6, Returns a array of primes, 2