# incremental sieve of eratosthenes
def primegen(): # http://stackoverflow.com/a/20660551
yield 2; yield 3 # prime (!) the pump
ps = primegen() # sieving primes
p = next(ps) and next(ps) # first sieving prime
D, q, c = {}, p*p, p # initialize
def add(m, s): # insert multiple/stride
while m in D: m += s # find unused multiple
D[m] = s # save multiple/stride
while True: # infinite list
c += 2 # next odd candidate
if c in D: # c is composite
s = D.pop(c) # fetch stride
add(c+s, s) # add next multiple
elif c < q: yield c # c is prime; yield it
else: # (c == q) # add sqrt(c) to sieve
add(c+p+p, p+p) # insert in sieve
p = next(ps) # next sieving prime
q = p * p # ... and its square
ps = primegen()
for i in range(10000):
p = next(ps)
print p
IyBpbmNyZW1lbnRhbCBzaWV2ZSBvZiBlcmF0b3N0aGVuZXMKCmRlZiBwcmltZWdlbigpOiAjIGh0dHA6Ly9zdGFja292ZXJmbG93LmNvbS9hLzIwNjYwNTUxCiAgICB5aWVsZCAyOyB5aWVsZCAzICAgICAgICAgICMgcHJpbWUgKCEpIHRoZSBwdW1wCiAgICBwcyA9IHByaW1lZ2VuKCkgICAgICAgICAgICMgc2lldmluZyBwcmltZXMKICAgIHAgPSBuZXh0KHBzKSBhbmQgbmV4dChwcykgIyBmaXJzdCBzaWV2aW5nIHByaW1lCiAgICBELCBxLCBjID0ge30sIHAqcCwgcCAgICAgICMgaW5pdGlhbGl6ZQogICAgZGVmIGFkZChtLCBzKTogICAgICAgICAgICAjIGluc2VydCBtdWx0aXBsZS9zdHJpZGUKICAgICAgICB3aGlsZSBtIGluIEQ6IG0gKz0gcyAgIyAgIGZpbmQgdW51c2VkIG11bHRpcGxlCiAgICAgICAgRFttXSA9IHMgICAgICAgICAgICAgICMgICBzYXZlIG11bHRpcGxlL3N0cmlkZQogICAgd2hpbGUgVHJ1ZTogICAgICAgICAgICAgICAjIGluZmluaXRlIGxpc3QKICAgICAgICBjICs9IDIgICAgICAgICAgICAgICAgIyBuZXh0IG9kZCBjYW5kaWRhdGUKICAgICAgICBpZiBjIGluIEQ6ICAgICAgICAgICAgIyBjIGlzIGNvbXBvc2l0ZQogICAgICAgICAgICBzID0gRC5wb3AoYykgICAgICAjICAgZmV0Y2ggc3RyaWRlCiAgICAgICAgICAgIGFkZChjK3MsIHMpICAgICAgICMgICBhZGQgbmV4dCBtdWx0aXBsZQogICAgICAgIGVsaWYgYyA8IHE6IHlpZWxkIGMgICAjIGMgaXMgcHJpbWU7IHlpZWxkIGl0CiAgICAgICAgZWxzZTogIyAoYyA9PSBxKSAgICAgICMgYWRkIHNxcnQoYykgdG8gc2lldmUKICAgICAgICAgICAgYWRkKGMrcCtwLCBwK3ApICAgIyAgIGluc2VydCBpbiBzaWV2ZQogICAgICAgICAgICBwID0gbmV4dChwcykgICAgICAjICAgbmV4dCBzaWV2aW5nIHByaW1lCiAgICAgICAgICAgIHEgPSBwICogcCAgICAgICAgICMgICAuLi4gYW5kIGl0cyBzcXVhcmUKCnBzID0gcHJpbWVnZW4oKQpmb3IgaSBpbiByYW5nZSgxMDAwMCk6CglwID0gbmV4dChwcykKcHJpbnQgcA==