The most efficient static sieve generator in python I have seen so far.
Returns the list of primes, that are not greater than n.
def eras(n):
siv=range(n+1)
siv[1]=0
sqn=int(round(n**0.5))
for i in range(2,sqn+1):
if siv[i]!=0:
siv[2*i:n/i*i+1:i]=[0]*(n/i-1)
return filter(None,siv)
david.raimosson
Replace line 7:
siv[2i:n/ii+1:i]=[0](n/i-1)
by
siv[i * i:n/ii+1:i]=[0]*(n/i-i+1)
to make it even faster.
vegaseat 1,720
Hmmm, I put it to the test ...
''' primelist_timing7.py
yet another primelist timing for speed
'''
import timeit
def time_function(stmt, setup):
"""use module timeit to time functions"""
# to enable garbage collection start setup with 'gc.enable();'
#setup = 'gc.enable();' + setup
t = timeit.Timer(stmt, setup)
# doing 10 passes * 100000 gives the time in microseconds/pass
# (a little less precise but saves time)
elapsed = (100000 * t.timeit(number=10))
print("%-18s --> %0.2f microseconds/pass" % (stmt, elapsed))
def eras(n):
"""
returns a list of primes 2 to n n
"""
siv = range(n+1)
siv[1] = 0
sqn = int(round(n**0.5))
for i in range(2, sqn+1):
if siv[i] != 0:
siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
return filter(None, siv)
def eras2(n):
"""
returns a list of primes 2 to n
"""
siv = range(n+1)
siv[1] = 0
sqn = int(round(n**0.5))
for i in range(2, sqn+1):
if siv[i] != 0:
#siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
siv[i*i:n/i*i+1:i] = [0]*(n/i-i+1)
return filter(None, siv)
def eras_dns(n):
"""
returns a list of primes 2 to < n
"""
sieve = [True] * (n>>1)
for x in range(3, int(n**0.5)+1, 2):
if sieve[x>>1]:
sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]
# time the function
stmt = 'eras(1000000)'
setup = 'from __main__ import eras'
time_function(stmt, setup)
# time the function
stmt = 'eras2(1000000)'
setup = 'from __main__ import eras2'
time_function(stmt, setup)
# time the function
stmt = 'eras_dns(1000000)'
setup = 'from __main__ import eras_dns'
time_function(stmt, setup)
# extra test
print(eras(61))
print(eras2(61))
print(eras_dns(61))
''' result with Python 2.7.3 ...
eras(1000000) --> 276458.51 microseconds/pass
eras2(1000000) --> 290727.66 microseconds/pass
eras_dns(1000000) --> 218466.05 microseconds/pass
'''
vegaseat 1,720
Actually, the fastest algorithm uses the Python module numpy ...
''' primelist_timing7a.py
yet another prime list timing for speed
using module numpy gives the fastest algorithm
tested with Python27
'''
import timeit
import numpy as np
def time_function(stmt, setup):
"""use module timeit to time functions"""
# to enable garbage collection start setup with 'gc.enable();'
#setup = 'gc.enable();' + setup
t = timeit.Timer(stmt, setup)
# doing 10 passes * 100000 gives the time in microseconds/pass
# (a little less precise but saves time)
elapsed = (100000 * t.timeit(number=10))
print("%-18s --> %0.2f microseconds/pass" % (stmt, elapsed))
def eras(n):
"""
returns a list of primes 2 to n n
"""
siv = range(n+1) # for Python3 use siv = list(range(n+1))
siv[1] = 0
sqn = int(round(n**0.5))
for i in range(2, sqn+1):
if siv[i] != 0:
siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
return filter(None, siv)
def eras2(n):
"""
returns a list of primes 2 to n
"""
siv = range(n+1) # for Python3 use siv = list(range(n+1))
siv[1] = 0
sqn = int(round(n**0.5))
for i in range(2, sqn+1):
if siv[i] != 0:
#siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
siv[i*i:n/i*i+1:i] = [0]*(n/i-i+1)
return filter(None, siv)
def eras_dns(n):
"""
returns a list of primes 2 to < n
"""
sieve = [True] * (n>>1)
for x in range(3, int(n**0.5)+1, 2):
if sieve[x>>1]:
sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]
def np_primes1(limit):
"""
returns a numpy array of primes, 2 <= p < limit
"""
# create a sieve of ones
is_prime = np.ones(limit + 1, dtype=np.bool)
for n in range(2, int(limit**0.5 + 1.5)):
if is_prime[n]:
is_prime[n*n::n] = 0
return np.nonzero(is_prime)[0][2:]
# time the function
stmt = 'eras(1000000)'
setup = 'from __main__ import eras'
time_function(stmt, setup)
# time the function
stmt = 'eras2(1000000)'
setup = 'from __main__ import eras2'
time_function(stmt, setup)
# time the function
stmt = 'eras_dns(1000000)'
setup = 'from __main__ import eras_dns'
time_function(stmt, setup)
# time the function
stmt = 'np_primes1(1000000)'
setup = 'from __main__ import np_primes1'
time_function(stmt, setup)
# extra test ...
print('-'*70)
print(eras(61))
print(eras2(61))
print(eras_dns(61+1))
print(list(np_primes1(61+1)))
''' result with Python 2.7.5 ...
eras(1000000) --> 140160.01 microseconds/pass
eras2(1000000) --> 160555.08 microseconds/pass
eras_dns(1000000) --> 120546.30 microseconds/pass
np_primes1(1000000) --> 12757.87 microseconds/pass
----------------------------------------------------------------------
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
'''
