For my timing mentioned (see also the Improving pure Python prime sieve by recurrence formula)
from time import clock
def rwh_primes1(n):
# https://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_primes_tjv(n):
# recurrence formula for length by amount1 and amount2 tjv
""" Returns a list of primes < n """
sieve = [True] * (n//2)
amount1 = n-10
amount2 = 6
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
## can you make recurrence formula for whole reciprocal?
sieve[i*i//2::i] = [False] * (amount1//amount2+1)
amount1-=4*i+4
amount2+=4
return [2] + [2*i+1 for i in xrange(1,n//2) if sieve[i]]
def rwh_primes_len(n):
""" Returns a list of primes < n """
sieve = [True] * (n//2)
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
sieve[i*i//2::i] = [False] * len(sieve[i*i//2::i])
return [2] + [2*i+1 for i in xrange(1,n//2) if sieve[i]]
def rwh_primes_any(n):
""" Returns a list of primes < n """
halfn=n//2
sieve = [True] * (halfn)
for i in range(3,int(n**0.5)+1,2):
if sieve[i//2]:
any(sieve.__setitem__(item,False) for item in range(i*i//2,halfn,i))
return [2] + [2*i+1 for i in xrange(1,n//2) if sieve[i]]
if __name__ == "__main__":
n = 1000000
print("rwh sieve1")
t=clock()
r=rwh_primes1(n)
print("Length %i, %s ms" %(len(r),1000*(clock()-t)))
print("rwh sieve with recurrence formula")
t=clock()
r=rwh_primes_tjv(n)
print("Length %i, %s ms" %(len(r),1000*(clock()-t)))
print("rwh sieve with len function")
t=clock()
r=rwh_primes_len(n)
print("Length %i, %s ms" %(len(r),1000*(clock()-t)))
print("rwh sieve with any with side effects")
t=clock()
r=rwh_primes_any(n)
print("Length %i, %s ms" %(len(r),1000*(clock()-t)))
raw_input( Ready )
""" Output:
rwh sieve1
Length 78498, 213.199442946 ms
rwh sieve with recurrence formula
Length 78498, 218.34143725 ms
rwh sieve with len function
Length 78498, 257.80008353 ms
rwh sieve with any with side effects
Length 78498, 829.977273648 ms
Ready
"""
Length function and all with setitem are not satisfactory alternatives, but the timings are here to demonstrate it.
rwh sieve with len function
Length 78498, 257.80008353 ms
rwh sieve with any with side effects
Length 78498, 829.977273648 ms