from itertools import islice
from timeit import Timer
import __main__
import math
def consume(iterator, n):
"Advance the iterator n-steps ahead. If n is none, consume entirely."
# Use functions that consume iterators at C speed.
if n is None:
# feed the entire iterator into a zero-length deque
collections.deque(iterator, maxlen=0)
else:
# advance to the empty slice starting at position n
next(islice(iterator, n, n), None)
def sieve():
'''
from http://c...content-available-to-author-only...e.com/
recipes/117119-sieve-of-eratosthenes/
original code by
David Eppstein, UC Irvine, 28 Feb 2002
'''
yield 2
D = {}
c = 3
while True:
s = D.pop(c, 0)
if s:
add(D,c + s,s)
else:
yield c
D[c*c] = 2*c
c += 2
def postponed_sieve():
'''
postponed sieve, by Will Ness
http://i...content-available-to-author-only...e.com/WFv4f
see also: http://stackoverflow.com/a/8871918/849891
'''
yield 2
D = {}
c = 3
ps = (p for p in sieve())
next(ps)
p = next(ps) # 3
q = p*p # 9
while True:
s = D.pop(c, 0)
if s:
add(D, c+s, s)
else:
if c < q:
yield c
else:
add(D, c+2*p, 2*p)
p = next(ps)
q = p*p
c += 2
def postponed_sieve2():
'''
postponed_sieve Recursive
'''
yield 2
yield 3
D = {}
c = 5
ps = (p for p in postponed_sieve2()) #recursive
next(ps) #skip 2
p = next(ps) # 3
q = p*p # 9
while True:
s = D.pop(c, 0)
if s:
add(D, c+s, s)
else:
if c < q:
yield c
else:
add(D, c+2*p, 2*p)
p = next(ps)
q = p*p
c += 2
def add(D,x,s):
while x in D: x += s
D[x] = s
def main1():
n = 100000
print(list(islice(postponed_sieve2(), n-1, n)))
def main2():
n = 100000
step = 100000
names = ('sieve','postponed_sieve2')
steps = 1
def times(n):
stmt='consume(f(),{n})'.format(n=n)
timer1 = Timer(stmt=stmt,
setup='from __main__ import consume,{name} as f'.format(name=names[0]))
timer2 = Timer(stmt=stmt,
setup='from __main__ import consume,{name} as f'.format(name=names[1]))
time1 = timer1.timeit(1)
time2 = timer2.timeit(1)
return (time1,time2)
time1,time2 = times(n)
print('{:^27} | {:^20}'.format(*names))
print('{n:>10s} {time1:>6s} {c1:>6s} | {time2:>6s} {c2:>6s}'.format(n='n',time1='time',time2='time',c1='',c2=''))
print('{n:10d} {time1:6.2f} | {time2:6.2f} '.format(n=n,time1=time1,c1=0,time2=time2,c2=0))
for i in range(steps):
np = n
n += step
time1p,time2p = time1,time2
time1,time2 = times(n)
c1 = math.log(time1/time1p,n/np)
c2 = math.log(time2/time2p,n/np)
print('{n:10d} {time1:6.2f} n^{c1:.4f} | {time2:6.2f} n^{c2:.4f}'.format(**locals()))
if __name__=='__main__':
main2()
ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGlzbGljZQpmcm9tIHRpbWVpdCBpbXBvcnQgVGltZXIKaW1wb3J0IF9fbWFpbl9fCmltcG9ydCBtYXRoCgoKZGVmIGNvbnN1bWUoaXRlcmF0b3IsIG4pOgogICAgIkFkdmFuY2UgdGhlIGl0ZXJhdG9yIG4tc3RlcHMgYWhlYWQuIElmIG4gaXMgbm9uZSwgY29uc3VtZSBlbnRpcmVseS4iCiAgICAjIFVzZSBmdW5jdGlvbnMgdGhhdCBjb25zdW1lIGl0ZXJhdG9ycyBhdCBDIHNwZWVkLgogICAgaWYgbiBpcyBOb25lOgogICAgICAgICMgZmVlZCB0aGUgZW50aXJlIGl0ZXJhdG9yIGludG8gYSB6ZXJvLWxlbmd0aCBkZXF1ZQogICAgICAgIGNvbGxlY3Rpb25zLmRlcXVlKGl0ZXJhdG9yLCBtYXhsZW49MCkKICAgIGVsc2U6CiAgICAgICAgIyBhZHZhbmNlIHRvIHRoZSBlbXB0eSBzbGljZSBzdGFydGluZyBhdCBwb3NpdGlvbiBuCiAgICAgICAgbmV4dChpc2xpY2UoaXRlcmF0b3IsIG4sIG4pLCBOb25lKQoKICAgICAgICAKZGVmIHNpZXZlKCk6CiAgICAnJycKICAgIGZyb20gaHR0cDovL2MuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tLwogICAgcmVjaXBlcy8xMTcxMTktc2lldmUtb2YtZXJhdG9zdGhlbmVzLwogICAgb3JpZ2luYWwgY29kZSBieQogICAgRGF2aWQgRXBwc3RlaW4sIFVDIElydmluZSwgMjggRmViIDIwMDIKICAgICcnJwogICAgeWllbGQgMgogICAgRCA9IHt9CiAgICBjID0gMwogICAgd2hpbGUgVHJ1ZToKICAgICAgICBzID0gRC5wb3AoYywgMCkKICAgICAgICBpZiBzOgogICAgICAgICAgICBhZGQoRCxjICsgcyxzKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHlpZWxkIGMKICAgICAgICAgICAgRFtjKmNdID0gMipjCiAgICAgICAgYyArPSAyCgoKZGVmIHBvc3Rwb25lZF9zaWV2ZSgpOgogICAgJycnCiAgICBwb3N0cG9uZWQgc2lldmUsIGJ5IFdpbGwgTmVzcwogICAgaHR0cDovL2kuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL1dGdjRmCiAgICBzZWUgYWxzbzogIGh0dHA6Ly9zdGFja292ZXJmbG93LmNvbS9hLzg4NzE5MTgvODQ5ODkxCiAgICAnJycKICAgIHlpZWxkIDIKICAgIEQgPSB7fQogICAgYyA9IDMKICAgIHBzID0gKHAgZm9yIHAgaW4gc2lldmUoKSkKICAgIG5leHQocHMpCiAgICBwID0gbmV4dChwcykgICAgICMgMwogICAgcSA9IHAqcCAgICAgICAgICAjIDkKICAgIHdoaWxlIFRydWU6CiAgICAgICAgcyA9IEQucG9wKGMsIDApCiAgICAgICAgaWYgczoKICAgICAgICAgICAgYWRkKEQsIGMrcywgcykKICAgICAgICBlbHNlOgogICAgICAgICAgICBpZiBjIDwgcToKICAgICAgICAgICAgICAgIHlpZWxkIGMKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIGFkZChELCBjKzIqcCwgMipwKQogICAgICAgICAgICAgICAgcCA9IG5leHQocHMpCiAgICAgICAgICAgICAgICBxID0gcCpwCiAgICAgICAgYyArPSAyCgoKZGVmIHBvc3Rwb25lZF9zaWV2ZTIoKToKICAgICcnJwogICAgcG9zdHBvbmVkX3NpZXZlIFJlY3Vyc2l2ZQogICAgJycnCiAgICB5aWVsZCAyCiAgICB5aWVsZCAzCiAgICBEID0ge30KICAgIGMgPSA1CiAgICBwcyA9IChwIGZvciBwIGluIHBvc3Rwb25lZF9zaWV2ZTIoKSkgI3JlY3Vyc2l2ZQogICAgbmV4dChwcykgI3NraXAgMgogICAgcCA9IG5leHQocHMpICMgMwogICAgcSA9IHAqcCAjIDkKICAgIHdoaWxlIFRydWU6CiAgICAgICAgcyA9IEQucG9wKGMsIDApCiAgICAgICAgaWYgczoKICAgICAgICAgICAgYWRkKEQsIGMrcywgcykKICAgICAgICBlbHNlOgogICAgICAgICAgICBpZiBjIDwgcToKICAgICAgICAgICAgICAgIHlpZWxkIGMKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIGFkZChELCBjKzIqcCwgMipwKQogICAgICAgICAgICAgICAgcCA9IG5leHQocHMpCiAgICAgICAgICAgICAgICBxID0gcCpwCiAgICAgICAgYyArPSAyCgoKZGVmIGFkZChELHgscyk6CiAgICB3aGlsZSB4IGluIEQ6IHggKz0gcwogICAgRFt4XSA9IHMKCgpkZWYgbWFpbjEoKToKICAgIG4gPSAxMDAwMDAKICAgIHByaW50KGxpc3QoaXNsaWNlKHBvc3Rwb25lZF9zaWV2ZTIoKSwgbi0xLCBuKSkpCgoKZGVmIG1haW4yKCk6CiAgICBuID0gMTAwMDAwCiAgICBzdGVwID0gMTAwMDAwCiAgICBuYW1lcyA9ICgnc2lldmUnLCdwb3N0cG9uZWRfc2lldmUyJykKICAgIHN0ZXBzID0gMQoKICAgIGRlZiB0aW1lcyhuKTogICAgICAgIAogICAgICAgIHN0bXQ9J2NvbnN1bWUoZigpLHtufSknLmZvcm1hdChuPW4pCiAgICAgICAgdGltZXIxID0gVGltZXIoc3RtdD1zdG10LAogICAgICAgICAgICAgICAgICAgICAgIHNldHVwPSdmcm9tIF9fbWFpbl9fIGltcG9ydCBjb25zdW1lLHtuYW1lfSBhcyBmJy5mb3JtYXQobmFtZT1uYW1lc1swXSkpCiAgICAgICAgdGltZXIyID0gVGltZXIoc3RtdD1zdG10LAogICAgICAgICAgICAgICAgICAgICAgIHNldHVwPSdmcm9tIF9fbWFpbl9fIGltcG9ydCBjb25zdW1lLHtuYW1lfSBhcyBmJy5mb3JtYXQobmFtZT1uYW1lc1sxXSkpCiAgICAgICAgdGltZTEgPSB0aW1lcjEudGltZWl0KDEpCiAgICAgICAgdGltZTIgPSB0aW1lcjIudGltZWl0KDEpCiAgICAgICAgcmV0dXJuICh0aW1lMSx0aW1lMikKCiAgICB0aW1lMSx0aW1lMiA9IHRpbWVzKG4pCiAgICBwcmludCgnezpeMjd9IHwgezpeMjB9Jy5mb3JtYXQoKm5hbWVzKSkKICAgIHByaW50KCd7bjo+MTBzfSB7dGltZTE6PjZzfSAgICB7YzE6PjZzfSB8IHt0aW1lMjo+NnN9ICAgIHtjMjo+NnN9Jy5mb3JtYXQobj0nbicsdGltZTE9J3RpbWUnLHRpbWUyPSd0aW1lJyxjMT0nJyxjMj0nJykpCiAgICBwcmludCgne246MTBkfSB7dGltZTE6Ni4yZn0gICAgICAgICAgIHwge3RpbWUyOjYuMmZ9ICAgICAgICAgJy5mb3JtYXQobj1uLHRpbWUxPXRpbWUxLGMxPTAsdGltZTI9dGltZTIsYzI9MCkpCiAgICAKICAgIAogICAgZm9yIGkgaW4gcmFuZ2Uoc3RlcHMpOgogICAgICAgIG5wID0gbgogICAgICAgIG4gKz0gc3RlcAogICAgICAgIHRpbWUxcCx0aW1lMnAgPSB0aW1lMSx0aW1lMgogICAgICAgIHRpbWUxLHRpbWUyID0gdGltZXMobikKICAgICAgICBjMSA9IG1hdGgubG9nKHRpbWUxL3RpbWUxcCxuL25wKQogICAgICAgIGMyID0gbWF0aC5sb2codGltZTIvdGltZTJwLG4vbnApCiAgICAgICAgcHJpbnQoJ3tuOjEwZH0ge3RpbWUxOjYuMmZ9ICBuXntjMTouNGZ9IHwge3RpbWUyOjYuMmZ9ICBuXntjMjouNGZ9Jy5mb3JtYXQoKipsb2NhbHMoKSkpCiAgICAgICAgCiAgICAKCgppZiBfX25hbWVfXz09J19fbWFpbl9fJzoKICAgIG1haW4yKCkK