from itertools import *
def wsieve(): # wheel-sieve, by Will Ness. ideone.com/mqO25A
wh11 = [ 2,4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,
4,8,6,4,6,2,4,6,2,6,6,4, 2,4,6,2,6,4,2,4,2,10,2,10]
cs = accumulate( chain( [11], cycle( wh11)))
yield( next( cs)) # cf. ideone.com/WFv4f
ps = wsieve() # codereview.stackexchange.com/q/92365/9064
p = next(ps) # 11
psq = p*p # 121
D = dict( zip( accumulate( chain( [0], wh11)), count(0))) # start from
mults = {}
for c in cs:
if c in mults: # a multiple of some prime:
wheel = mults.pop(c)
for m in wheel:
if not m in mults: # skip to the prime's next multiple
break
mults[m] = wheel # and put that back in
elif c < psq:
yield c # a prime
else: # (c == psq) is the next prime's square
# map (p*) (roll wh from p) = roll (wh*p) from (p*p)
x = [p*d for d in wh11]
i = D[ (p-11) % 210]
# accumulate( chain( [psq+x[i]], cycle( x[i+1:] + x[:i+1])))
for xi in (x[i:] + x[:i]):
psq += xi
wheel = count( psq, p*210) # 48 counts for 1 accumulate:
for m in wheel: # ... NOT worth it!
if not m in mults:
break
mults[m] = wheel
p = next(ps) ; psq = p*p
def primes():
yield from (2, 3, 5, 7)
yield from wsieve()
def tdprimes():
yield from (2,3)
for c in count(5,2):
for d in count(3,2):
if d*d > c:
yield c
break
if (c % d) == 0:
break
if True:
n = 2000000
print(n)
print( list( islice( primes() , n-1, n+1)))
ZnJvbSBpdGVydG9vbHMgaW1wb3J0ICoKCmRlZiB3c2lldmUoKTogICAgICAgIyB3aGVlbC1zaWV2ZSwgYnkgV2lsbCBOZXNzLiAgICBpZGVvbmUuY29tL21xTzI1QQogICAgd2gxMSA9IFsgMiw0LDIsNCw2LDIsNiw0LDIsNCw2LDYsIDIsNiw0LDIsNiw0LDYsOCw0LDIsNCwyLAogICAgICAgICAgICAgNCw4LDYsNCw2LDIsNCw2LDIsNiw2LDQsIDIsNCw2LDIsNiw0LDIsNCwyLDEwLDIsMTBdCiAgICBjcyA9IGFjY3VtdWxhdGUoIGNoYWluKCBbMTFdLCBjeWNsZSggd2gxMSkpKQogICAgeWllbGQoIG5leHQoIGNzKSkgICMgY2YuIGlkZW9uZS5jb20vV0Z2NGYKICAgIHBzID0gd3NpZXZlKCkgICAgICAjICAgICBjb2RlcmV2aWV3LnN0YWNrZXhjaGFuZ2UuY29tL3EvOTIzNjUvOTA2NAogICAgcCA9IG5leHQocHMpICAgICAgICMgMTEKICAgIHBzcSA9IHAqcCAgICAgICAgICAjIDEyMQogICAgRCA9IGRpY3QoIHppcCggYWNjdW11bGF0ZSggY2hhaW4oIFswXSwgd2gxMSkpLCBjb3VudCgwKSkpICAgIyBzdGFydCBmcm9tCiAgICBtdWx0cyA9IHt9CiAgICBmb3IgYyBpbiBjczoKICAgICAgICBpZiBjIGluIG11bHRzOiAgICAgICAgICAgICAgICAjIGEgbXVsdGlwbGUgb2Ygc29tZSBwcmltZToKICAgICAgICAgICAgd2hlZWwgPSBtdWx0cy5wb3AoYykgCiAgICAgICAgICAgIGZvciBtIGluIHdoZWVsOiAKICAgICAgICAgICAgICAgIGlmIG5vdCBtIGluIG11bHRzOiAgICAjIHNraXAgdG8gdGhlIHByaW1lJ3MgbmV4dCBtdWx0aXBsZQogICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIG11bHRzW21dID0gd2hlZWwgICAgICAgICAgIyBhbmQgcHV0IHRoYXQgYmFjayBpbgogICAgICAgIGVsaWYgYyA8IHBzcTogICAgICAgICAgICAgIAogICAgICAgICAgICB5aWVsZCBjICAgICAgICAgICAgICAgICAgICMgYSBwcmltZQogICAgICAgIGVsc2U6ICAgICAgICAgICAgICAgICAgICAgICAgICMgKGMgPT0gcHNxKSBpcyB0aGUgbmV4dCBwcmltZSdzIHNxdWFyZSAgCiAgICAgICAgICAgICMgbWFwIChwKikgKHJvbGwgd2ggZnJvbSBwKSA9IHJvbGwgKHdoKnApIGZyb20gKHAqcCkKICAgICAgICAgICAgeCA9IFtwKmQgZm9yIGQgaW4gd2gxMV0KICAgICAgICAgICAgaSA9IERbIChwLTExKSAlIDIxMF0KICAgICAgICAgICAgIyBhY2N1bXVsYXRlKCBjaGFpbiggW3BzcSt4W2ldXSwgY3ljbGUoIHhbaSsxOl0gKyB4WzppKzFdKSkpCiAgICAgICAgICAgIGZvciB4aSBpbiAoeFtpOl0gKyB4WzppXSk6CiAgICAgICAgICAgICAgICBwc3EgKz0geGkKICAgICAgICAgICAgICAgIHdoZWVsID0gY291bnQoIHBzcSwgcCoyMTApICAjIDQ4IGNvdW50cyBmb3IgMSBhY2N1bXVsYXRlOgogICAgICAgICAgICAgICAgZm9yIG0gaW4gd2hlZWw6ICAgICAgICAgICAgICMgICAgICAgICAgICAgIC4uLiBOT1Qgd29ydGggaXQhCiAgICAgICAgICAgICAgICAgICAgaWYgbm90IG0gaW4gbXVsdHM6IAogICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICAgICAgbXVsdHNbbV0gPSB3aGVlbAogICAgICAgICAgICBwID0gbmV4dChwcykgOyBwc3EgPSBwKnAgCgpkZWYgcHJpbWVzKCk6IAoJeWllbGQgZnJvbSAoMiwgMywgNSwgNykKCXlpZWxkIGZyb20gd3NpZXZlKCkgIAoJCmRlZiB0ZHByaW1lcygpOgoJeWllbGQgZnJvbSAoMiwzKQoJZm9yIGMgaW4gY291bnQoNSwyKToKCQlmb3IgZCBpbiBjb3VudCgzLDIpOgoJCQlpZiBkKmQgPiBjOgoJCQkJeWllbGQgYwoJCQkJYnJlYWsKCQkJaWYgKGMgJSBkKSA9PSAwOgoJCQkJYnJlYWsKCQkJCmlmIFRydWU6ICAgICAgICAgICAgICAgICAgIAogICAgbiA9IDIwMDAwMDAKICAgIHByaW50KG4pIAogICAgcHJpbnQoIGxpc3QoIGlzbGljZSggIHByaW1lcygpICwgbi0xLCBuKzEpKSkgICA=