time_python_prime_generation.sh

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