def primegen():
"""'Infinite' prime generator - a litte slow
about 7.4 sec for 10^6 primes
90 sec for 10^7 primes
"""
yield from (2,3)
blocked = {}
ps = primegen()
candidate = prime = next(ps) and next(ps)
prime_squared = prime * prime
while True:
candidate += 2
if candidate in blocked:
step = blocked.pop(candidate)
elif candidate == prime_squared:
step = prime + prime
prime = next(ps)
prime_squared = prime * prime
else:
yield candidate
continue
m = candidate + step
while m in blocked:
m += step
blocked[m] = step
p = primegen()
for i in range(10):
print(next(p))
ZGVmIHByaW1lZ2VuKCk6CiAgICAiIiInSW5maW5pdGUnIHByaW1lIGdlbmVyYXRvciAtIGEgbGl0dGUgc2xvdwogICAgICAgIGFib3V0IDcuNCBzZWMgZm9yIDEwXjYgcHJpbWVzCiAgICAgICAgICAgICAgOTAgIHNlYyBmb3IgMTBeNyBwcmltZXMKICAgICIiIgogICAgeWllbGQgZnJvbSAoMiwzKQogICAgYmxvY2tlZCA9IHt9CiAgICBwcyA9IHByaW1lZ2VuKCkKICAgIGNhbmRpZGF0ZSA9IHByaW1lID0gbmV4dChwcykgYW5kIG5leHQocHMpCiAgICBwcmltZV9zcXVhcmVkID0gcHJpbWUgKiBwcmltZQogICAgd2hpbGUgVHJ1ZToKICAgICAgICBjYW5kaWRhdGUgKz0gMgogICAgICAgIGlmIGNhbmRpZGF0ZSBpbiBibG9ja2VkOgogICAgICAgICAgICBzdGVwID0gYmxvY2tlZC5wb3AoY2FuZGlkYXRlKQogICAgICAgIGVsaWYgY2FuZGlkYXRlID09IHByaW1lX3NxdWFyZWQ6CiAgICAgICAgICAgIHN0ZXAgPSBwcmltZSArIHByaW1lCiAgICAgICAgICAgIHByaW1lID0gbmV4dChwcykKICAgICAgICAgICAgcHJpbWVfc3F1YXJlZCA9IHByaW1lICogcHJpbWUKICAgICAgICBlbHNlOgogICAgICAgICAgICB5aWVsZCBjYW5kaWRhdGUKICAgICAgICAgICAgY29udGludWUKICAgICAgICBtID0gY2FuZGlkYXRlICsgc3RlcAogICAgICAgIHdoaWxlIG0gaW4gYmxvY2tlZDoKICAgICAgICAgICAgbSArPSBzdGVwCiAgICAgICAgYmxvY2tlZFttXSA9IHN0ZXAKICAgICAgICAKcCA9IHByaW1lZ2VuKCkKZm9yIGkgaW4gcmFuZ2UoMTApOgoJcHJpbnQobmV4dChwKSkK