Skip to content

@Veedrac /time_python_prime_generation.sh
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
SETUP="
import sys
from itertools import compress
def vprimes(maximum=10**6):
maxidx = maximum//2
sieve = [True] * maxidx # 2, 3, 5, 7... might be prime
j = 0
for i in range(1, int(maxidx**0.5)+1):
j += 4*i
if sieve[i]:
step = 2*i + 1
sieve[j::step] = [False] * -(-(maxidx-j) // step)
# compress sieve
primes = list(compress(range(1, maximum, 2), sieve))
primes[0] = 2
return primes
def vprimes_2_switch(maximum=10**6):
maxidx = maximum//2
sieve = [True] * maxidx # 2, 3, 5, 7... might be prime
j = 0
for i in range(1, int(maxidx**0.5)+1):
j += 4*i
if sieve[i]:
step = 2*i + 1
sieve[j::step] = [False] * -(-(maxidx-j) // step)
# compress sieve
if sys.version_info >= (3, 0):
primes = list(compress(range(1, maximum, 2), sieve))
else:
primes = [idx*2+1 for idx, isprime in enumerate(sieve) if isprime]
primes[0] = 2
return primes
def rwh_primes(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
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_primes2(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
def rwh_primes_py3(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
sieve = [True] * n
for i in range(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 range(3,n,2) if sieve[i]]
def rwh_primes2_py3(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n//3)
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)//3) ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
"
echo "Veedrac's; Python 2"
python2 -m timeit -s "$SETUP" "vprimes(10**6)"
# 10 loops, best of 3: 74.8 msec per loop
python2 -m timeit -s "$SETUP" "vprimes_2_switch(10**6)"
# 10 loops, best of 3: 31.9 msec per loop
echo
echo "Veedrac's; Python 3"
python3 -m timeit -s "$SETUP" "vprimes(10**6)"
# 10 loops, best of 3: 20 msec per loop
python3 -m timeit -s "$SETUP" "vprimes_2_switch(10**6)"
# 10 loops, best of 3: 19.8 msec per loop
echo
echo "Robert William Hanks'; Python 2"
python2 -m timeit -s "$SETUP" "rwh_primes(10**6)"
# 10 loops, best of 3: 32.9 msec per loop
python2 -m timeit -s "$SETUP" "rwh_primes2(10**6)"
# 10 loops, best of 3: 21.3 msec per loop
echo
echo "Robert William Hanks'; basic Python 3 edit"
python3 -m timeit -s "$SETUP" "rwh_primes_py3(10**6)"
# 10 loops, best of 3: 43.5 msec per loop
python3 -m timeit -s "$SETUP" "rwh_primes2_py3(10**6)"
# 10 loops, best of 3: 34.7 msec per loop
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.