fork download 
  1. import itertools
  2. import math
  3.  
  4. def primes():
  5.     yield 2
  6.     n = 3
  7.     p = []
  8.     while True:
  9.             # --------- this is exhaustive trial division -------------------
  10.             # testing needlessly by all preceding primes
  11.             #    -- this confirms O'Neill's complexity for Turner's sieve - *BUT*    NB!
  12.             #       *BUT* in an IMPERATVE setting of Python;
  13.             #       in Haskell for bigger n's it's WORSE than n^2 --
  14.             #            the operational overhead trumps over the calculational one
  15.             #                              (which is the ONLY thing that she took into account)
  16.  
  17.         #if not any( n % f == 0 for f in p ):                        #  2k: 1.02s-5.9MB    7k:12.59s-5.9MB
  18.                                                                      #                 n^2.01
  19.         #if not any( n % f == 0 for f in p if f*f <= n ):            #  2k: 0.58s-5.9MB   10k:14.43s-6.2MB
  20.         #                                                            #                 n^2.00
  21.  
  22.             # -------- this is optimal trial division - one-by-one generation -------------
  23.             #   - refetching primes to test by anew for each new candidate
  24.  
  25.         if not any( n % f == 0 for f in       
  26.                      itertools.takewhile(lambda f: f*f <= n, p) ):   # 10k: 0.80s-5.9MB   50k: 7.22s-5.9MB
  27.             yield n                                                  #                 n^1.37
  28.             p.append( n )
  29.         n += 2
  30.  
  31.   # ------------ this is optimal trial division - segmented generation, ----------------
  32.   # prefetching primes prefixes to test by once for each segment between primes squares
  33.  
  34. def pprimes():                #  10k: 0.41s-6.2MB    50k:3.57s-5.9MB    100k:9.42s-5.9MB !+++++++
  35.     yield 2                   #                 n^1.34              n^1.40
  36.     k = 0; p = []; 
  37.     n = 3; q = 9;
  38.     while True:
  39.         ps = p[:k]
  40.         xs = itertools.filterfalse( lambda x: any( x % f == 0 for f in ps ), 
  41.                                     range(n,q,2) )
  42.         for x in xs:
  43.             yield x 
  44.             p.append( x )
  45.  
  46.         n = q+2; k += 1; q = p[k]*p[k]
  47.  
  48. # ------------ this is code from Wikipedia Sieve of Eratosthenes page ---------------
  49.  
  50. def eratosthenes_sieve(n):         #    10k: 0.05s-6.2MB   100k:0.57s-6.7MB   500k:3.72s-6.7MB   1m:MEMOUT
  51.                                    #                   n^1.05             n^1.17
  52.  
  53.     m = n*math.ceil( math.log(n)*1.1 )       #    10k:*11  100k:*13  1m:*16  
  54.     candidates = list(range(m+1))    
  55.     fin = int(m**0.5)
  56.  
  57.     for i in range(2, fin+1):
  58.         if candidates[i]:
  59.             candidates[2*i::i] = [None] * len(candidates[2*i::i])
  60.  
  61.     # Filter out non-primes and return the list.
  62.     return [i for i in candidates[2:] if i]
  63.  
  64.  
  65. n=10000; print( eratosthenes_sieve(n)[n-10:n] )  
  66.  
  67. #n=10000; print( list( itertools.islice( pprimes(), n-5, n))) 
  68.  
  69. #print( list( itertools.islice( pprimes(), 10)))
Success #stdin #stdout 0.05s 6248KB
comments (?)
stdin 
Standard input is empty
stdout 
[104677, 104681, 104683, 104693, 104701, 104707, 104711, 104717, 104723, 104729]
https://ideone.com/dUIx6
language:
Python 3 (python  3.12)
created:
14 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!