some analysis of millar rabin (http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) vs sieve based (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) prime list generation

gistfile1.py

from functools import wraps
from datetime import datetime


def time(f):
    @wraps(f)
    def inner(*args, **kwargs):
        start = datetime.now()
        res = f(*args, **kwargs)
        delta = datetime.now() - start
        print delta
        return res
    return inner


def memo(f):
    cache = {}

    @wraps(f)
    def inner(*args, **kwargs):
        key = str(args) + str(kwargs)
        try:
            return cache[key]
        except KeyError:
            cache[key] = f(*args, **kwargs)
            return cache[key]
    return inner


def sieve(n):
    li = [2] + range(3, n, 2)
    cur = li.pop(0)
    res = []
    while(cur < n**.5):
        li = [x for x in li if x % cur != 0]
        res += [cur]
        cur = li.pop(0)
    return res + [cur] + li


def millar(n):
    if n == 2:
        return True
    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d /= 2

    def check(a, s, d, n):
        c = a**d % n
        r = 0
        if c == 1:
            return True
        while r < s:
            if c == n - 1:
                return True
            c = c**2 % n
            r += 1
        return False
    return reduce(lambda x, y: x and y,
                  map(lambda x: check(x, s, d, n),
                      range(2, min(n, 4))
                      )
                  )


def millarlist(n):
    return filter(lambda x: millar(x), range(2, n))


def est(n):
    print len(millarlist(n)) - len(sieve(n))

print len(sieve(999999999))