Instantly share code, notes, and snippets.

Veedrac/time_python_prime_generation.sh Last active Aug 29, 2015

What would you like to do?
 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