fork download
copy 
  1. from itertools import islice
  2. from timeit import Timer
  3. import __main__
  4. import math
  5.  
  6.  
  7. def consume(iterator, n):
  8.     "Advance the iterator n-steps ahead. If n is none, consume entirely."
  9.     # Use functions that consume iterators at C speed.
  10.     if n is None:
  11.         # feed the entire iterator into a zero-length deque
  12.         collections.deque(iterator, maxlen=0)
  13.     else:
  14.         # advance to the empty slice starting at position n
  15.         next(islice(iterator, n, n), None)
  16.  
  17.  
  18. def sieve():
  19.     '''
  20.     from http://c...content-available-to-author-only...e.com/
  21.     recipes/117119-sieve-of-eratosthenes/
  22.     original code by
  23.     David Eppstein, UC Irvine, 28 Feb 2002
  24.     '''
  25.     yield 2
  26.     D = {}
  27.     c = 3
  28.     while True:
  29.         s = D.pop(c, 0)
  30.         if s:
  31.             add(D,c + s,s)
  32.         else:
  33.             yield c
  34.             D[c*c] = 2*c
  35.         c += 2
  36.  
  37.  
  38. def postponed_sieve():
  39.     '''
  40.     postponed sieve, by Will Ness
  41.     http://i...content-available-to-author-only...e.com/WFv4f
  42.     see also:  http://stackoverflow.com/a/8871918/849891
  43.     '''
  44.     yield 2
  45.     D = {}
  46.     c = 3
  47.     ps = (p for p in sieve())
  48.     next(ps)
  49.     p = next(ps)     # 3
  50.     q = p*p          # 9
  51.     while True:
  52.         s = D.pop(c, 0)
  53.         if s:
  54.             add(D, c+s, s)
  55.         else:
  56.             if c < q:
  57.                 yield c
  58.             else:
  59.                 add(D, c+2*p, 2*p)
  60.                 p = next(ps)
  61.                 q = p*p
  62.         c += 2
  63.  
  64.  
  65. def postponed_sieve2():
  66.     '''
  67.     postponed_sieve Recursive
  68.     '''
  69.     yield 2
  70.     yield 3
  71.     D = {}
  72.     c = 5
  73.     ps = (p for p in postponed_sieve2()) #recursive
  74.     next(ps) #skip 2
  75.     p = next(ps) # 3
  76.     q = p*p # 9
  77.     while True:
  78.         s = D.pop(c, 0)
  79.         if s:
  80.             add(D, c+s, s)
  81.         else:
  82.             if c < q:
  83.                 yield c
  84.             else:
  85.                 add(D, c+2*p, 2*p)
  86.                 p = next(ps)
  87.                 q = p*p
  88.         c += 2
  89.  
  90.  
  91. def add(D,x,s):
  92.     while x in D: x += s
  93.     D[x] = s
  94.  
  95.  
  96. def main1():
  97.     n = 100000
  98.     print(list(islice(postponed_sieve2(), n-1, n)))
  99.  
  100.  
  101. def main2():
  102.     n = 100000
  103.     step = 100000
  104.     names = ('sieve','postponed_sieve2')
  105.     steps = 1
  106.  
  107.     def times(n):        
  108.         stmt='consume(f(),{n})'.format(n=n)
  109.         timer1 = Timer(stmt=stmt,
  110.                        setup='from __main__ import consume,{name} as f'.format(name=names[0]))
  111.         timer2 = Timer(stmt=stmt,
  112.                        setup='from __main__ import consume,{name} as f'.format(name=names[1]))
  113.         time1 = timer1.timeit(1)
  114.         time2 = timer2.timeit(1)
  115.         return (time1,time2)
  116.  
  117.     time1,time2 = times(n)
  118.     print('{:^27} | {:^20}'.format(*names))
  119.     print('{n:>10s} {time1:>6s}    {c1:>6s} | {time2:>6s}    {c2:>6s}'.format(n='n',time1='time',time2='time',c1='',c2=''))
  120.     print('{n:10d} {time1:6.2f}           | {time2:6.2f}         '.format(n=n,time1=time1,c1=0,time2=time2,c2=0))
  121.  
  122.  
  123.     for i in range(steps):
  124.         np = n
  125.         n += step
  126.         time1p,time2p = time1,time2
  127.         time1,time2 = times(n)
  128.         c1 = math.log(time1/time1p,n/np)
  129.         c2 = math.log(time2/time2p,n/np)
  130.         print('{n:10d} {time1:6.2f}  n^{c1:.4f} | {time2:6.2f}  n^{c2:.4f}'.format(**locals()))
  131.  
  132.  
  133.  
  134.  
  135. if __name__=='__main__':
  136.     main2()
  137.  
Success #stdin #stdout 7.7s 6320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
           sieve            |   postponed_sieve2  
         n   time           |   time          
    100000   1.33           |   1.09         
    200000   2.99  n^1.1746 |   2.35  n^1.1095
https://ideone.com/z9dHG
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!