def primes():      # http://r...content-available-to-author-only...e.org/wiki/Sieve_of_Eratosthenes
    for x in [2,3,5,7]:  yield x            #  #Infinite_generator_with_a_faster_algorithm
    ps = (p for p in primes())              # additional primes supply
    p = ps.next() and ps.next()             # discard 2, then get 3
    q = p*p                                 # 9 - square of next prime to be put
    sieve = {}                              #       into sieve dict
    n = 9                                   # the candidate number
    while True:
        if n not in sieve:                  # is not a multiple of previously recorded primes
            if n < q:                       # n is prime
                yield n  
            else:
                add(sieve, q + 2*p, 2*p)    # n==p*p: for prime p, under p*p + 2*p, 
                p = ps.next()               #         add 2*p as incremental step
                q = p*p
        else:
            s = sieve.pop(n)
            add(sieve, n + s, s)
        n += 2                              # work on odds only

def add(sieve,next,step):
    while next in sieve:                    # ensure each entry is unique
        next += step
    sieve[next] = step                      # next non-marked multiple of a prime

def test():                                 # 100k: 0.73s-4.7MB
   ps = primes()                            # 200k: 1.55s-4.7MB   n^1.09 !!
   for i in xrange(1,1000000): ps.next()    # 400k: 3.28s-4.7MB   n^1.08 !!!
   print ps.next()                          # 1m:   8.86s-4.7MB   n^1.08 !!!   15485863

test()