# from:  http://r...content-available-to-author-only...e.org/wiki/Sieve_of_Eratosthenes#Infinite_generator_with_a_faster_algorithm
 
def primes():
    yield 2; yield 3; yield 5; yield 7;
    bps = (p for p in primes())             # additional primes supply
    p = next(bps) and next(bps)             # discard 2, then get 3
    q = p * p                               # 9 - square of next prime to be put
    sieve = {}                              #       into sieve dict
    n = 9                                   # the initial candidate number
    while True:
        if n not in sieve:                  # is not a multiple of previously recorded primes
            if n < q:
                yield n                     # n is prime
            else:
                p2 = p + p                  # n == p * p: for prime p, add p * p + 2 * p,
                sieve[q + p2] = p2          #               with 2 * p as incremental step
                p = next(bps); q = p * p    # advance base prime and next prime to be put                
        else:
            s = sieve.pop(n); nxt = n + s   # n is composite, advance
            while nxt in sieve: nxt += s    # ensure each entry is unique
            sieve[nxt] = s                  # next non-marked multiple of this prime
        n += 2                              # work on odds only
 
ps = primes()                               # 100k: 0.52s-7.9MB
for n in xrange(1, 1000000): next(ps)       # 200k: 1.12s-7.9MB   n^1.11 !!
print next(ps)                              # 400k: 2.39s-7.9MB   n^1.09 !!!
                                            # 1m:   6.01s-7.9MB   n^1.10 !!!   15485863

IyBmcm9tOiAgaHR0cDovL3IuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUub3JnL3dpa2kvU2lldmVfb2ZfRXJhdG9zdGhlbmVzI0luZmluaXRlX2dlbmVyYXRvcl93aXRoX2FfZmFzdGVyX2FsZ29yaXRobQoKZGVmIHByaW1lcygpOgogICAgeWllbGQgMjsgeWllbGQgMzsgeWllbGQgNTsgeWllbGQgNzsKICAgIGJwcyA9IChwIGZvciBwIGluIHByaW1lcygpKSAgICAgICAgICAgICAjIGFkZGl0aW9uYWwgcHJpbWVzIHN1cHBseQogICAgcCA9IG5leHQoYnBzKSBhbmQgbmV4dChicHMpICAgICAgICAgICAgICMgZGlzY2FyZCAyLCB0aGVuIGdldCAzCiAgICBxID0gcCAqIHAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyA5IC0gc3F1YXJlIG9mIG5leHQgcHJpbWUgdG8gYmUgcHV0CiAgICBzaWV2ZSA9IHt9ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAgICAgICBpbnRvIHNpZXZlIGRpY3QKICAgIG4gPSA5ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHRoZSBpbml0aWFsIGNhbmRpZGF0ZSBudW1iZXIKICAgIHdoaWxlIFRydWU6CiAgICAgICAgaWYgbiBub3QgaW4gc2lldmU6ICAgICAgICAgICAgICAgICAgIyBpcyBub3QgYSBtdWx0aXBsZSBvZiBwcmV2aW91c2x5IHJlY29yZGVkIHByaW1lcwogICAgICAgICAgICBpZiBuIDwgcToKICAgICAgICAgICAgICAgIHlpZWxkIG4gICAgICAgICAgICAgICAgICAgICAjIG4gaXMgcHJpbWUKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHAyID0gcCArIHAgICAgICAgICAgICAgICAgICAjIG4gPT0gcCAqIHA6IGZvciBwcmltZSBwLCBhZGQgcCAqIHAgKyAyICogcCwKICAgICAgICAgICAgICAgIHNpZXZlW3EgKyBwMl0gPSBwMiAgICAgICAgICAjICAgICAgICAgICAgICAgd2l0aCAyICogcCBhcyBpbmNyZW1lbnRhbCBzdGVwCiAgICAgICAgICAgICAgICBwID0gbmV4dChicHMpOyBxID0gcCAqIHAgICAgIyBhZHZhbmNlIGJhc2UgcHJpbWUgYW5kIG5leHQgcHJpbWUgdG8gYmUgcHV0ICAgICAgICAgICAgICAgIAogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHMgPSBzaWV2ZS5wb3Aobik7IG54dCA9IG4gKyBzICAgIyBuIGlzIGNvbXBvc2l0ZSwgYWR2YW5jZQogICAgICAgICAgICB3aGlsZSBueHQgaW4gc2lldmU6IG54dCArPSBzICAgICMgZW5zdXJlIGVhY2ggZW50cnkgaXMgdW5pcXVlCiAgICAgICAgICAgIHNpZXZlW254dF0gPSBzICAgICAgICAgICAgICAgICAgIyBuZXh0IG5vbi1tYXJrZWQgbXVsdGlwbGUgb2YgdGhpcyBwcmltZQogICAgICAgIG4gKz0gMiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgd29yayBvbiBvZGRzIG9ubHkKCnBzID0gcHJpbWVzKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAxMDBrOiAwLjUycy03LjlNQgpmb3IgbiBpbiB4cmFuZ2UoMSwgMTAwMDAwMCk6IG5leHQocHMpICAgICAgICMgMjAwazogMS4xMnMtNy45TUIgICBuXjEuMTEgISEKcHJpbnQgbmV4dChwcykgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIDQwMGs6IDIuMzlzLTcuOU1CICAgbl4xLjA5ICEhIQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgMW06ICAgNi4wMXMtNy45TUIgICBuXjEuMTAgISEhICAgMTU0ODU4NjM=