def primeSieve (primes = None, start = 0, length = 4096):
    # primes = primes or [ (3, 3) ]
    primes = primes or []
    sieve  = [ 0 ] * length

    # Sieve known / existing primes
    last_prime = 3
    for i, (p, x) in enumerate(primes):
        while x < (start + length) * 2 + 1:
            sieve[(x - 1 - start) / 2] = 1
            x += p * 2
        primes[i] = (p, x)
        if p > last_prime:
            last_prime = p

    # Apply sieve forwards until we hit length
    for i in range((last_prime - 1 - start) / 2, length, 1):
        if sieve[i] == 0:
            p = i * 2 + start + 1
            x = p
            while x < (start + length) * 2 + 1:
                sieve[(x - 1 - start) / 2] = 1
                x += p * 2
            primes += [(p, x)]
    return primes

def naivePrimes (N):
    primes = []
    for i in range(3, N * 2 + 1, 2):
        isPrime = True
        for p in primes:
            if i % p == 0:
                isPrime = False
                break
        if isPrime:
            primes += [i]
    return primes


if __name__ == '__main__':
    SIEVE_SIZE = 60000
    NTH_PRIME  = 10001

    import time
    t0 = time.time()

    first = lambda (a,b): a
    primes = map(first, primeSieve(None, 0, SIEVE_SIZE))

    t1 = time.time()

    print(primes)

    t2 = time.time()

    print("\nSIEVE:")
    print("Generated %d primes (first: %s, last: %s)"%(len(primes), primes[0], primes[-1]))
    print("Generated in %s seconds"%(t1 - t0))
    print("Printed   in %s seconds"%(t2 - t1))

    print("%dth prime is %s"%(NTH_PRIME, primes[NTH_PRIME]))

    t0 = time.time()

    primes2 = naivePrimes(SIEVE_SIZE)

    t1 = time.time()

    print("\nNAIVE:")
    print("Generated %d primes (first: %s, last: %s)"%(len(primes2), primes2[0], primes2[-1]))
    print("Generated in %s seconds"%(t1 - t0))
    print("%dth prime is %s"%(NTH_PRIME, primes2[NTH_PRIME]))