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()   

ZGVmIHByaW1lcygpOiAgICAgICMgaHR0cDovL3IuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUub3JnL3dpa2kvU2lldmVfb2ZfRXJhdG9zdGhlbmVzCiAgICBmb3IgeCBpbiBbMiwzLDUsN106ICB5aWVsZCB4ICAgICAgICAgICAgIyAgI0luZmluaXRlX2dlbmVyYXRvcl93aXRoX2FfZmFzdGVyX2FsZ29yaXRobQogICAgcHMgPSAocCBmb3IgcCBpbiBwcmltZXMoKSkgICAgICAgICAgICAgICMgYWRkaXRpb25hbCBwcmltZXMgc3VwcGx5CiAgICBwID0gcHMubmV4dCgpIGFuZCBwcy5uZXh0KCkgICAgICAgICAgICAgIyBkaXNjYXJkIDIsIHRoZW4gZ2V0IDMKICAgIHEgPSBwKnAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIDkgLSBzcXVhcmUgb2YgbmV4dCBwcmltZSB0byBiZSBwdXQKICAgIHNpZXZlID0ge30gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjICAgICAgIGludG8gc2lldmUgZGljdAogICAgbiA9IDkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgdGhlIGNhbmRpZGF0ZSBudW1iZXIKICAgIHdoaWxlIFRydWU6CiAgICAgICAgaWYgbiBub3QgaW4gc2lldmU6ICAgICAgICAgICAgICAgICAgIyBpcyBub3QgYSBtdWx0aXBsZSBvZiBwcmV2aW91c2x5IHJlY29yZGVkIHByaW1lcwogICAgICAgICAgICBpZiBuIDwgcTogICAgICAgICAgICAgICAgICAgICAgICMgbiBpcyBwcmltZQogICAgICAgICAgICAgICAgeWllbGQgbiAgCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBhZGQoc2lldmUsIHEgKyAyKnAsIDIqcCkgICAgIyBuPT1wKnA6IGZvciBwcmltZSBwLCB1bmRlciBwKnAgKyAyKnAsIAogICAgICAgICAgICAgICAgcCA9IHBzLm5leHQoKSAgICAgICAgICAgICAgICMgICAgICAgICBhZGQgMipwIGFzIGluY3JlbWVudGFsIHN0ZXAKICAgICAgICAgICAgICAgIHEgPSBwKnAKICAgICAgICBlbHNlOgogICAgICAgICAgICBzID0gc2lldmUucG9wKG4pCiAgICAgICAgICAgIGFkZChzaWV2ZSwgbiArIHMsIHMpCiAgICAgICAgbiArPSAyICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB3b3JrIG9uIG9kZHMgb25seQoKZGVmIGFkZChzaWV2ZSxuZXh0LHN0ZXApOgogICAgd2hpbGUgbmV4dCBpbiBzaWV2ZTogICAgICAgICAgICAgICAgICAgICMgZW5zdXJlIGVhY2ggZW50cnkgaXMgdW5pcXVlCiAgICAgICAgbmV4dCArPSBzdGVwCiAgICBzaWV2ZVtuZXh0XSA9IHN0ZXAgICAgICAgICAgICAgICAgICAgICAgIyBuZXh0IG5vbi1tYXJrZWQgbXVsdGlwbGUgb2YgYSBwcmltZQoKZGVmIHRlc3QoKTogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIDEwMGs6IDAuNzNzLTQuN01CCiAgIHBzID0gcHJpbWVzKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAyMDBrOiAxLjU1cy00LjdNQiAgIG5eMS4wOSAhIQogICBmb3IgaSBpbiB4cmFuZ2UoMSwxMDAwMDAwKTogcHMubmV4dCgpICAgICMgNDAwazogMy4yOHMtNC43TUIgICBuXjEuMDggISEhCiAgIHByaW50IHBzLm5leHQoKSAgICAgICAgICAgICAgICAgICAgICAgICAgIyAxbTogICA4Ljg2cy00LjdNQiAgIG5eMS4wOCAhISEgICAxNTQ4NTg2MwoKdGVzdCgpICAg