wheel = [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]
wsize = 48
def primes():
yield from (2, 3, 5, 7)
yield from wsieve()
def wsieve(): # wheel-sieve, by Will Ness. cf. ideone.com/WFv4f
yield 11 # cf. http://stackoverflow.com/a/10733621/849891
mults = {} # http://stackoverflow.com/a/19391111/849891
ps = wsieve() # base primes
p = next(ps) # 11
psq = p*p # 121
c = 11 # the last Candidate
i = 0 # position on the wheel for next c: 11+2 =: 13
cbase = 11 # base coprimes stream, to gen the mults for primes in it
ibase = 0 # position on wheel for cbase==p
while True:
c += wheel[i] # next candidate from coprimes
i = (i+1) % wsize # on the wheel
if c not in mults: # c's not a multiple of any base prime:
if c < psq: # hence, a prime
yield c ; continue # ; or
else: # (c==psq) # is the next base prime's square:
while not cbase == p: # skip on base coprimes until
cbase += wheel[ibase] # the base prime from rec supply
ibase = (ibase+1) % wsize
# map (p*) $ scanl (+) p (d:w) =
# = scanl (\c d->c+p*d) (p*p) (d:w)
# add(mults, c, ibase, p) # add NEXT mult of p after c==psq
j = ibase ; pbase = p # go from ibase on the wheel
p = next(ps) ; psq = p*p
else: # `c` is a mult of prev-seen base prime:
(j,pbase) = mults.pop(c)
# add(mults, c, j, pbase) # add NEXT mult of pbase after c
m = c + pbase*wheel[j] ; j = (j+1) % wsize
while m in mults:
m += pbase*wheel[j] ; j = (j+1) % wsize
mults[m] = (j,pbase) # into the mults dict
import itertools # 100K 0.42s-8.7MB 800K 4.00s-8.7MB n^1.1
# 200K 0.88s-8.7MB 1M 5.10s-8.7MB
if True: # 400K 1.88s-8.7MB n^1.1 2M 10.88s-8.7MB n^1.1
n = 800000
print(n)
print( list( itertools.islice( (p for p in primes() ), n-1, n+1)))
d2hlZWwgPSBbMiw0LDIsNCw2LDIsNiw0LDIsNCw2LDYsMiw2LDQsMiw2LDQsNiw4LDQsMiw0LDIsCiAgICAgICAgIDQsOCw2LDQsNiwyLDQsNiwyLDYsNiw0LDIsNCw2LDIsNiw0LDIsNCwyLDEwLDIsMTBdCndzaXplID0gNDgKCmRlZiBwcmltZXMoKTogCgl5aWVsZCBmcm9tICgyLCAzLCA1LCA3KQoJeWllbGQgZnJvbSB3c2lldmUoKQoKZGVmIHdzaWV2ZSgpOiAgICAgICAjIHdoZWVsLXNpZXZlLCBieSBXaWxsIE5lc3MuIGNmLiBpZGVvbmUuY29tL1dGdjRmCiAgICB5aWVsZCAxMSAgICAgICAgIyBjZi4gaHR0cDovL3N0YWNrb3ZlcmZsb3cuY29tL2EvMTA3MzM2MjEvODQ5ODkxICAgICAKICAgIG11bHRzID0ge30gICAgICAjICAgICBodHRwOi8vc3RhY2tvdmVyZmxvdy5jb20vYS8xOTM5MTExMS84NDk4OTEKICAgIHBzID0gd3NpZXZlKCkgICAjIGJhc2UgcHJpbWVzCiAgICBwID0gbmV4dChwcykgICAgIyAxMQogICAgcHNxID0gcCpwICAgICAgICMgMTIxCiAgICBjID0gMTEgICAgICAgICAgIyB0aGUgbGFzdCBDYW5kaWRhdGUKICAgIGkgPSAwICAgICAgICAgICAjIHBvc2l0aW9uIG9uIHRoZSB3aGVlbCBmb3IgbmV4dCBjOiAxMSsyID06IDEzCiAgICBjYmFzZSA9IDExICAgICAgIyBiYXNlIGNvcHJpbWVzIHN0cmVhbSwgdG8gZ2VuIHRoZSBtdWx0cyBmb3IgcHJpbWVzIGluIGl0CiAgICBpYmFzZSA9IDAgICAgICAgIyBwb3NpdGlvbiBvbiB3aGVlbCBmb3IgY2Jhc2U9PXAKICAgIHdoaWxlIFRydWU6CiAgICAgICAgYyArPSB3aGVlbFtpXSAgICAgICAgICAgICAgICAgIyBuZXh0IGNhbmRpZGF0ZSBmcm9tIGNvcHJpbWVzCiAgICAgICAgaSA9IChpKzEpICUgd3NpemUgICAgICAgICAgICAgIyAgIG9uIHRoZSB3aGVlbAogICAgICAgIGlmIGMgbm90IGluIG11bHRzOiAgICAgICAgICAgICMgYydzIG5vdCBhIG11bHRpcGxlIG9mIGFueSBiYXNlIHByaW1lOgogICAgICAgICAgICBpZiBjIDwgcHNxOiAgICAgICAgICAgICAgICMgICBoZW5jZSwgYSBwcmltZSAKICAgICAgICAgICAgICAgIHlpZWxkIGMgOyBjb250aW51ZSAgICAjICAgICAgICAgICAgICAgICAgOyBvcgogICAgICAgICAgICBlbHNlOiAgICMgKGM9PXBzcSkgICAgICAgICMgICBpcyB0aGUgbmV4dCBiYXNlIHByaW1lJ3Mgc3F1YXJlOgogICAgICAgICAgICAgICAgd2hpbGUgbm90IGNiYXNlID09IHA6ICAgICAgICAjIHNraXAgb24gYmFzZSBjb3ByaW1lcyB1bnRpbAogICAgICAgICAgICAgICAgCWNiYXNlICs9IHdoZWVsW2liYXNlXSAgICAjICB0aGUgYmFzZSBwcmltZSBmcm9tIHJlYyBzdXBwbHkKICAgICAgICAgICAgICAgIAlpYmFzZSA9IChpYmFzZSsxKSAlIHdzaXplCiAgICAgICAgICAgICAgICAjIG1hcCAocCopICQgc2NhbmwgKCspIHAgKGQ6dykgPQogICAgICAgICAgICAgICAgIyAgICAgICAgICA9IHNjYW5sIChcYyBkLT5jK3AqZCkgKHAqcCkgKGQ6dykgCiAgICAgICAgICAgICAgICAjIGFkZChtdWx0cywgYywgaWJhc2UsIHApICAgICMgYWRkIE5FWFQgbXVsdCBvZiBwIGFmdGVyIGM9PXBzcQogICAgICAgICAgICAgICAgaiA9IGliYXNlIDsgcGJhc2UgPSBwICAgICAgICAjICAgZ28gZnJvbSBpYmFzZSBvbiB0aGUgd2hlZWwKICAgICAgICAgICAgICAgIHAgPSBuZXh0KHBzKSA7IHBzcSA9IHAqcAogICAgICAgIGVsc2U6ICAgICAgICAgICAgICAgICAgICAgICAgICMgYGNgIGlzIGEgbXVsdCBvZiBwcmV2LXNlZW4gYmFzZSBwcmltZToKICAgICAgICAgICAgKGoscGJhc2UpID0gbXVsdHMucG9wKGMpICAgICAgICAKICAgICAgICAgICAgIyBhZGQobXVsdHMsIGMsIGosIHBiYXNlKSAgICAgICAgIyBhZGQgTkVYVCBtdWx0IG9mIHBiYXNlIGFmdGVyIGMKICAgICAgICBtID0gYyArIHBiYXNlKndoZWVsW2pdIDsgaiA9IChqKzEpICUgd3NpemUKICAgICAgICB3aGlsZSBtIGluIG11bHRzOiAgCiAgICAgICAgICAgIG0gKz0gcGJhc2Uqd2hlZWxbal0gOyBqID0gKGorMSkgJSB3c2l6ZQogICAgICAgIG11bHRzW21dID0gKGoscGJhc2UpICAgICAgICAgICAgICAgICAjICAgICAgICAgICAgaW50byB0aGUgbXVsdHMgZGljdAogICAgICAgIAppbXBvcnQgaXRlcnRvb2xzICAgICAgICMgMTAwSyAgMC40MnMtOC43TUIgICAgICAgICAgODAwSyAgNC4wMHMtOC43TUIgbl4xLjEKICAgICAgICAgICAgICAgICAgICAgICAjIDIwMEsgIDAuODhzLTguN01CICAgICAgICAgIDFNICAgIDUuMTBzLTguN01CCmlmIFRydWU6ICAgICAgICAgICAgICAgIyA0MDBLICAxLjg4cy04LjdNQiAgbl4xLjEgICAyTSAgIDEwLjg4cy04LjdNQiBuXjEuMQogICAgbiA9IDgwMDAwMAogICAgcHJpbnQobikgCiAgICBwcmludCggbGlzdCggaXRlcnRvb2xzLmlzbGljZSggKHAgZm9yIHAgaW4gcHJpbWVzKCkgKSwgbi0xLCBuKzEpKSkgICA=