'''http://c...content-available-to-author-only...e.com/recipes/117119/'''
from itertools import count,islice,groupby
from timeit import Timer
import collections
from heapq import merge
import __main__
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 primes1():
D = {}
for q in count(2):
p = D.pop(q, None)
if p:
x = p + q
while x in D: x += p
D[x] = p
else:
D[q*q] = q
yield q
def primes2():
seq = count(2)
while True:
p = next(seq)
seq = filter(p.__rmod__, seq) #get not multiples of p (as item % p == 0 for multiples)
yield p
def primes3():
p = 2
yield p
sifter = count(p*p,p)
s = next(sifter)
for p in count(p+1):
if p==s: # this p is sieved out
#print('s: {}'.format(s))
s = next(sifter)
else:
yield p # this is prime
#print('p: {}'.format(p))
sifter = (k for k, g in groupby(merge(sifter,count(p*p,p)))) #add this serie to the sifter: p*p, p*(p+1), p*(p+2), ...
#--Debug for primes4--
##'''
##Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
##postponed sieve, by Will Ness
##See also: http://i...content-available-to-author-only...e.com/WFv4f
##'''
##def primes4(debug=False,level=0):
## '''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
## achieved by postponing the addition of stepping information for a prime
## into the dict until that prime's square is seen amongst the candidates,
## and not a moment sooner.
## Having much smaller dict, performance and empirical time complexity improve too.
## http://i...content-available-to-author-only...e.com/WFv4f'''
##
## name = '{0}'.format(level)
##
## print = __builtins__.print if debug else lambda *p: None
##
## print('{name}: yield 2'.format(name=name)); yield 2
## print('{name}: yield 3'.format(name=name)); yield 3
## print('{name}: yield 5'.format(name=name)); yield 5
## print('{name}: yield 7'.format(name=name)); yield 7
## D = {}
## c = 9; print('{name}: c = {c}'.format(name=name,c=c))
## ps = (p for p in primes4(debug=debug,level=level+1)); print('{name}: Creating subiterator'.format(name=name))
## temp = next(ps)
## print('{name}: skip {temp}'.format(name=name,temp=temp)) #skip 2
## p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
## q = p*p; print('{name}: q = {q}'.format(name=name,q=q)) # 9
## while True:
## print('{name}: D = {D}'.format(name=name,D=D))
## if c not in D:
## print('{name}: c not in D'.format(name=name))
## if c < q:
## print('{name}: c<q'.format(name=name))
## print('{name}: yield c = {c}'.format(name=name,c=c))
## yield c
## else:
## print('{name}: c=q'.format(name=name))
## x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p))
## p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
## q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
## else:
## print('{name}: c in D'.format(name=name))
## s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
## x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
## c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
'''
Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
postponed sieve, by Will Ness
See also: http://i...content-available-to-author-only...e.com/WFv4f
'''
def primes4():
'''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
achieved by postponing the addition of stepping information for a prime
into the dict until that prime's square is seen amongst the candidates,
and not a moment sooner.
Having much smaller dict, performance and empirical time complexity improve too.
http://i...content-available-to-author-only...e.com/WFv4f'''
yield 2
yield 3
yield 5
yield 7
D = {}
c = 9
ps = (p for p in primes4())
next(ps) #skip 2
p = next(ps) # 3
q = p*p # 9
while True:
if c not in D:
if c < q:
yield c
else:
x = add(D,c+2*p,2*p)
p = next(ps)
q = p*p
else:
s = D.pop(c)
x = add(D,c+s,s)
c += 2;
def add(D,x,s):
while x in D:
x += s
D[x] = s
return x
def primes5():
'''Save values instead of using recursive generator call'''
primes = [] #values memory
yield 2; primes.append(2)
yield 3; primes.append(3)
yield 5; primes.append(5)
yield 7; primes.append(7)
D = {}
c = 9
ps = (p for p in iter(primes)) #here we used memoized values
next(ps) #skip 2
p = next(ps) # 3
q = p*p # 9
while True:
if c not in D:
if c < q:
yield c; primes.append(c)
else:
x = add(D,c+2*p,2*p)
p = next(ps)
q = p*p
else:
s = D.pop(c)
x = add(D,c+s,s)
c += 2;
funcs = ['primes1','primes4','primes5']
number = 1 #number of runs
upper = 100000 #the upper limit for primes
def main():
'''Complexity comparison between different functions'''
for func_name in funcs:
f = getattr(__main__,func_name)
print('---')
print(f.__name__)
print(list(islice(f(),20)))
timer = Timer('consume(f(),{upper})'.format(upper=upper),
'from __main__ import {name} as f, consume'.format(name=func_name))
result = timer.timeit(number=number)
print('t: {}'.format(result/number))
def main1():
'''Just '''
n = 20
next(islice(primes4(debug=True), n, n), None) #consume n values
if __name__=='__main__':
main()