'''http://c...content-available-to-author-only...e.com/recipes/117119/'''
 
from itertools import count,islice,groupby
from timeit import Timer
import collections
from heapq import merge
import __main__
 
 
'''
Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
postponed sieve, by Will Ness
See also: http://i...content-available-to-author-only...e.com/WFv4f
'''        
def primes4(debug=False,level=0):
    '''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
    achieved by postponing the addition of stepping information for a prime
    into the dict until that prime's square is seen amongst the candidates,
    and not a moment sooner.
    Having much smaller dict, performance and empirical time complexity improve too.
    http://i...content-available-to-author-only...e.com/WFv4f'''
 
    name = '{0}'.format(level)
 
    print = __builtins__.print if debug else lambda *p: None
 
    print('{name}: yield 2'.format(name=name)); yield 2 
    print('{name}: yield 3'.format(name=name)); yield 3
    print('{name}: yield 5'.format(name=name)); yield 5
    print('{name}: yield 7'.format(name=name)); yield 7 
    D = {}              
    c = 9; print('{name}: c = {c}'.format(name=name,c=c))
    ps = (p for p in primes4(debug=debug,level=level+1)); print('{name}: Creating subiterator'.format(name=name))
    temp = next(ps)
    print('{name}: skip {temp}'.format(name=name,temp=temp))     #skip 2 
    p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
    q = p*p; print('{name}: q = {q}'.format(name=name,q=q))      # 9
    while True:
        print('{name}: D = {D}'.format(name=name,D=D))
        if c not in D:
            print('{name}: c not in D'.format(name=name))
            if c < q:
                print('{name}: c<q'.format(name=name))
                print('{name}: yield c = {c}'.format(name=name,c=c))
                yield c 
            else:
                print('{name}: c=q'.format(name=name))
                x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p)) 
                p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
                q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
        else:
            print('{name}: c in D'.format(name=name))
            s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
            x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
        c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
 
 
def add(D,x,s):
    while x in D:
        x += s
    D[x] = s
    return x
 
 
def main1():
    '''Just '''
    n = 20
    next(islice(primes4(debug=True), n, n), None) #consume n values     
 
 
if __name__=='__main__':
    main1()

JycnaHR0cDovL2MuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL3JlY2lwZXMvMTE3MTE5LycnJwoKZnJvbSBpdGVydG9vbHMgaW1wb3J0IGNvdW50LGlzbGljZSxncm91cGJ5CmZyb20gdGltZWl0IGltcG9ydCBUaW1lcgppbXBvcnQgY29sbGVjdGlvbnMKZnJvbSBoZWFwcSBpbXBvcnQgbWVyZ2UKaW1wb3J0IF9fbWFpbl9fCgoKJycnClVuc2Vyc3RhbmRpbmcgY29kZSBmcm9tIGhlcmU6IGh0dHA6Ly9zdGFja292ZXJmbG93LmNvbS9hLzEwNzMzNjIxLzg2MjM4MApwb3N0cG9uZWQgc2lldmUsIGJ5IFdpbGwgTmVzcwpTZWUgYWxzbzogaHR0cDovL2kuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL1dGdjRmCicnJyAgICAgICAgCmRlZiBwcmltZXM0KGRlYnVnPUZhbHNlLGxldmVsPTApOgogICAgJycnVGhlIHNwYWNlIGNvbXBsZXhpdHkgaXMgbmVlZGxlc3NseSBPKG4pLiBPKHNxcnQobikpIGlzIGVub3VnaCBpbmRlZWQsCiAgICBhY2hpZXZlZCBieSBwb3N0cG9uaW5nIHRoZSBhZGRpdGlvbiBvZiBzdGVwcGluZyBpbmZvcm1hdGlvbiBmb3IgYSBwcmltZQogICAgaW50byB0aGUgZGljdCB1bnRpbCB0aGF0IHByaW1lJ3Mgc3F1YXJlIGlzIHNlZW4gYW1vbmdzdCB0aGUgY2FuZGlkYXRlcywKICAgIGFuZCBub3QgYSBtb21lbnQgc29vbmVyLgogICAgSGF2aW5nIG11Y2ggc21hbGxlciBkaWN0LCBwZXJmb3JtYW5jZSBhbmQgZW1waXJpY2FsIHRpbWUgY29tcGxleGl0eSBpbXByb3ZlIHRvby4KICAgIGh0dHA6Ly9pLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS9XRnY0ZicnJwoKICAgIG5hbWUgPSAnezB9Jy5mb3JtYXQobGV2ZWwpCiAgICAKICAgIHByaW50ID0gX19idWlsdGluc19fLnByaW50IGlmIGRlYnVnIGVsc2UgbGFtYmRhICpwOiBOb25lCgogICAgcHJpbnQoJ3tuYW1lfTogeWllbGQgMicuZm9ybWF0KG5hbWU9bmFtZSkpOyB5aWVsZCAyIAogICAgcHJpbnQoJ3tuYW1lfTogeWllbGQgMycuZm9ybWF0KG5hbWU9bmFtZSkpOyB5aWVsZCAzCiAgICBwcmludCgne25hbWV9OiB5aWVsZCA1Jy5mb3JtYXQobmFtZT1uYW1lKSk7IHlpZWxkIDUKICAgIHByaW50KCd7bmFtZX06IHlpZWxkIDcnLmZvcm1hdChuYW1lPW5hbWUpKTsgeWllbGQgNyAKICAgIEQgPSB7fSAgICAgICAgICAgICAgCiAgICBjID0gOTsgcHJpbnQoJ3tuYW1lfTogYyA9IHtjfScuZm9ybWF0KG5hbWU9bmFtZSxjPWMpKQogICAgcHMgPSAocCBmb3IgcCBpbiBwcmltZXM0KGRlYnVnPWRlYnVnLGxldmVsPWxldmVsKzEpKTsgcHJpbnQoJ3tuYW1lfTogQ3JlYXRpbmcgc3ViaXRlcmF0b3InLmZvcm1hdChuYW1lPW5hbWUpKQogICAgdGVtcCA9IG5leHQocHMpCiAgICBwcmludCgne25hbWV9OiBza2lwIHt0ZW1wfScuZm9ybWF0KG5hbWU9bmFtZSx0ZW1wPXRlbXApKSAgICAgI3NraXAgMiAKICAgIHAgPSBuZXh0KHBzKTsgcHJpbnQoJ3tuYW1lfTogcCA9IHtwfScuZm9ybWF0KG5hbWU9bmFtZSxwPXApKSAjIDMKICAgIHEgPSBwKnA7IHByaW50KCd7bmFtZX06IHEgPSB7cX0nLmZvcm1hdChuYW1lPW5hbWUscT1xKSkgICAgICAjIDkKICAgIHdoaWxlIFRydWU6CiAgICAgICAgcHJpbnQoJ3tuYW1lfTogRCA9IHtEfScuZm9ybWF0KG5hbWU9bmFtZSxEPUQpKQogICAgICAgIGlmIGMgbm90IGluIEQ6CiAgICAgICAgICAgIHByaW50KCd7bmFtZX06IGMgbm90IGluIEQnLmZvcm1hdChuYW1lPW5hbWUpKQogICAgICAgICAgICBpZiBjIDwgcToKICAgICAgICAgICAgICAgIHByaW50KCd7bmFtZX06IGM8cScuZm9ybWF0KG5hbWU9bmFtZSkpCiAgICAgICAgICAgICAgICBwcmludCgne25hbWV9OiB5aWVsZCBjID0ge2N9Jy5mb3JtYXQobmFtZT1uYW1lLGM9YykpCiAgICAgICAgICAgICAgICB5aWVsZCBjIAogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcHJpbnQoJ3tuYW1lfTogYz1xJy5mb3JtYXQobmFtZT1uYW1lKSkKICAgICAgICAgICAgICAgIHggPSBhZGQoRCxjKzIqcCwyKnApOyBwcmludCgne25hbWV9OiBEW3t4fV09e3N9Jy5mb3JtYXQobmFtZT1uYW1lLHg9eCxzPTIqcCkpIAogICAgICAgICAgICAgICAgcCA9IG5leHQocHMpOyBwcmludCgne25hbWV9OiBwID0ge3B9Jy5mb3JtYXQobmFtZT1uYW1lLHA9cCkpCiAgICAgICAgICAgICAgICBxID0gcCpwOyBwcmludCgne25hbWV9OiBxID0ge3F9Jy5mb3JtYXQobmFtZT1uYW1lLHE9cSkpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgcHJpbnQoJ3tuYW1lfTogYyBpbiBEJy5mb3JtYXQobmFtZT1uYW1lKSkKICAgICAgICAgICAgcyA9IEQucG9wKGMpOyBwcmludCgne25hbWV9OiBwb3BwaW5nIGZyb20gRDogcyA9IHtzfScuZm9ybWF0KG5hbWU9bmFtZSxzPXMpKQogICAgICAgICAgICB4ID0gYWRkKEQsIGMrcywgcyk7IHByaW50KCd7bmFtZX06IGFkZGluZyB0byBEW3t4fV09e3N9Jy5mb3JtYXQobmFtZT1uYW1lLHg9eCxzPWMrcykpCiAgICAgICAgYyArPSAyOyBwcmludCgne25hbWV9OiBjKz0yIC0+IGM9e2N9Jy5mb3JtYXQobmFtZT1uYW1lLGM9YykpCgoKZGVmIGFkZChELHgscyk6CiAgICB3aGlsZSB4IGluIEQ6CiAgICAgICAgeCArPSBzCiAgICBEW3hdID0gcwogICAgcmV0dXJuIHgKCgpkZWYgbWFpbjEoKToKICAgICcnJ0p1c3QgJycnCiAgICBuID0gMjAKICAgIG5leHQoaXNsaWNlKHByaW1lczQoZGVidWc9VHJ1ZSksIG4sIG4pLCBOb25lKSAjY29uc3VtZSBuIHZhbHVlcyAgICAgCgoKaWYgX19uYW1lX189PSdfX21haW5fXyc6CiAgICBtYWluMSgp