fork download
copy 
  1. '''http://c...content-available-to-author-only...e.com/recipes/117119/'''
  2.  
  3. from itertools import count,islice,groupby
  4. from timeit import Timer
  5. import collections
  6. from heapq import merge
  7. import __main__
  8.  
  9.  
  10. def consume(iterator, n):
  11.     "Advance the iterator n-steps ahead. If n is none, consume entirely."
  12.     # Use functions that consume iterators at C speed.
  13.     if n is None:
  14.         # feed the entire iterator into a zero-length deque
  15.         collections.deque(iterator, maxlen=0)
  16.     else:
  17.         # advance to the empty slice starting at position n
  18.         next(islice(iterator, n, n), None)
  19.  
  20.  
  21. def primes1():
  22.     D = {}
  23.     for q in count(2):
  24.         p = D.pop(q, None)
  25.         if p:
  26.             x = p + q
  27.             while x in D: x += p
  28.             D[x] = p
  29.         else:
  30.             D[q*q] = q
  31.             yield q
  32.  
  33.  
  34. def primes2():
  35.     seq = count(2)
  36.     while True:
  37.         p = next(seq)
  38.         seq = filter(p.__rmod__, seq) #get not multiples of p (as item % p == 0 for multiples)
  39.         yield p
  40.  
  41.  
  42.  
  43. def primes3():
  44.     p = 2
  45.     yield p
  46.     sifter = count(p*p,p)
  47.     s = next(sifter)
  48.     for p in count(p+1):
  49.         if p==s: # this p is sieved out
  50.             #print('s: {}'.format(s))
  51.             s = next(sifter)
  52.         else:
  53.             yield p # this is prime
  54.             #print('p: {}'.format(p))
  55.             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), ...
  56.  
  57.  
  58. #--Debug for primes4--
  59. ##'''
  60. ##Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
  61. ##postponed sieve, by Will Ness
  62. ##See also: http://i...content-available-to-author-only...e.com/WFv4f
  63. ##'''        
  64. ##def primes4(debug=False,level=0):
  65. ##    '''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
  66. ##    achieved by postponing the addition of stepping information for a prime
  67. ##    into the dict until that prime's square is seen amongst the candidates,
  68. ##    and not a moment sooner.
  69. ##    Having much smaller dict, performance and empirical time complexity improve too.
  70. ##    http://i...content-available-to-author-only...e.com/WFv4f'''
  71. ##
  72. ##    name = '{0}'.format(level)
  73. ##    
  74. ##    print = __builtins__.print if debug else lambda *p: None
  75. ##
  76. ##    print('{name}: yield 2'.format(name=name)); yield 2 
  77. ##    print('{name}: yield 3'.format(name=name)); yield 3
  78. ##    print('{name}: yield 5'.format(name=name)); yield 5
  79. ##    print('{name}: yield 7'.format(name=name)); yield 7 
  80. ##    D = {}              
  81. ##    c = 9; print('{name}: c = {c}'.format(name=name,c=c))
  82. ##    ps = (p for p in primes4(debug=debug,level=level+1)); print('{name}: Creating subiterator'.format(name=name))
  83. ##    temp = next(ps)
  84. ##    print('{name}: skip {temp}'.format(name=name,temp=temp))     #skip 2 
  85. ##    p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
  86. ##    q = p*p; print('{name}: q = {q}'.format(name=name,q=q))      # 9
  87. ##    while True:
  88. ##        print('{name}: D = {D}'.format(name=name,D=D))
  89. ##        if c not in D:
  90. ##            print('{name}: c not in D'.format(name=name))
  91. ##            if c < q:
  92. ##                print('{name}: c<q'.format(name=name))
  93. ##                print('{name}: yield c = {c}'.format(name=name,c=c))
  94. ##                yield c 
  95. ##            else:
  96. ##                print('{name}: c=q'.format(name=name))
  97. ##                x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p)) 
  98. ##                p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
  99. ##                q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
  100. ##        else:
  101. ##            print('{name}: c in D'.format(name=name))
  102. ##            s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
  103. ##            x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
  104. ##        c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
  105.  
  106.  
  107. '''
  108. Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
  109. postponed sieve, by Will Ness
  110. See also: http://i...content-available-to-author-only...e.com/WFv4f
  111. '''        
  112. def primes4():
  113.     '''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
  114.     achieved by postponing the addition of stepping information for a prime
  115.     into the dict until that prime's square is seen amongst the candidates,
  116.     and not a moment sooner.
  117.     Having much smaller dict, performance and empirical time complexity improve too.
  118.     http://i...content-available-to-author-only...e.com/WFv4f'''
  119.  
  120.     yield 2 
  121.     yield 3
  122.     yield 5
  123.     yield 7 
  124.     D = {}              
  125.     c = 9
  126.     ps = (p for p in primes4())
  127.     next(ps) #skip 2 
  128.     p = next(ps) # 3
  129.     q = p*p # 9
  130.     while True:
  131.         if c not in D:
  132.             if c < q:
  133.                 yield c 
  134.             else:
  135.                 x = add(D,c+2*p,2*p)
  136.                 p = next(ps)
  137.                 q = p*p
  138.         else:
  139.             s = D.pop(c)
  140.             x = add(D,c+s,s)
  141.         c += 2;
  142.  
  143. def add(D,x,s):
  144.     while x in D:
  145.         x += s
  146.     D[x] = s
  147.     return x
  148.  
  149.  
  150. def primes5():
  151.     '''Save values instead of using recursive generator call'''
  152.     primes = [] #values memory
  153.     yield 2; primes.append(2) 
  154.     yield 3; primes.append(3)
  155.     yield 5; primes.append(5)
  156.     yield 7; primes.append(7) 
  157.     D = {}              
  158.     c = 9
  159.     ps = (p for p in iter(primes)) #here we used memoized values
  160.     next(ps) #skip 2 
  161.     p = next(ps) # 3
  162.     q = p*p # 9
  163.     while True:
  164.         if c not in D:
  165.             if c < q:
  166.                 yield c; primes.append(c) 
  167.             else:
  168.                 x = add(D,c+2*p,2*p)
  169.                 p = next(ps)
  170.                 q = p*p
  171.         else:
  172.             s = D.pop(c)
  173.             x = add(D,c+s,s)
  174.         c += 2;
  175.  
  176.  
  177. funcs = ['primes1','primes4','primes5']
  178.  
  179.  
  180. number = 1 #number of runs
  181. upper = 100000 #the upper limit for primes
  182.  
  183. def main():
  184.     '''Complexity comparison between different functions'''
  185.     for func_name in funcs:
  186.         f = getattr(__main__,func_name)
  187.         print('---')
  188.         print(f.__name__)
  189.         print(list(islice(f(),20)))
  190.         timer = Timer('consume(f(),{upper})'.format(upper=upper),
  191.                       'from __main__ import {name} as f, consume'.format(name=func_name))
  192.         result = timer.timeit(number=number)
  193.         print('t: {}'.format(result/number))
  194.  
  195. def main1():
  196.     '''Just '''
  197.     n = 20
  198.     next(islice(primes4(debug=True), n, n), None) #consume n values        
  199.  
  200.  
  201.  
  202. if __name__=='__main__':
  203.     main()
  204.  
Success #stdin #stdout 4.92s 6032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
---
primes1
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
t: 2.59932017326
---
primes4
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
t: 1.13969612122
---
primes5
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
t: 1.18516302109
https://ideone.com/xeke4
language:
Python 3 (python  3.9.5)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!