fork download
copy 
  1. import math
  2.  
  3. def prime_sieve(limit):
  4.     primes = [1 for x in xrange(limit)]
  5.     primes[0] = 0
  6.     primes[1] = 0
  7.     imax = int(math.sqrt(limit) + 1)
  8.  
  9.     i = 2
  10.     while (i < imax):
  11.         j = i * i            # was: i+i
  12.         while j < limit:
  13.             primes[j] = 0
  14.             j += i
  15.         while True:
  16.             i += 1
  17.             if primes[i] == 1:
  18.                 break
  19.     return primes
  20.  
  21. ### s = prime_sieve(2000000)
  22. ### print( len( list( (i for i in xrange(len(s)) if s[i] == 1))))
  23.  
  24. # --i+i--                                 # --i*i--
  25. #   N       n                             #    N       n  
  26. #  10k     1229  0.02s-7.9M               #
  27. #  2mln  148933  1.13s-7.9M               #  2mln  148933  1.12s-7.9M  
  28. #  4mln  283146  2.30s-7.9M  n^1.11       #  4mln  283146  2.25s-7.9M  n^1.09
  29. #  8mln  539777  4.58s-7.9M  n^1.07       #  8mln  539777  4.38s-7.9M  n^1.03
  30. # 16mln 1031130  9.12s-7.9M  n^1.06       # 16mln 1031130  8.82s-7.9M  n^1.08
  31.  
  32.  
  33.  
  34. def sieve(max):
  35.   primes = range(2,max+1)
  36.   for i in primes:
  37.     # print i, 
  38.     j = i                        # was: j = 2
  39.     while i * j <= primes[-1]:
  40.       if i * j in primes:
  41.         primes.remove(i*j)
  42.       j += 1
  43.   return primes
  44.  
  45. count = 0
  46. for x in sieve(30000):
  47.     count += 1
  48. print count
  49.  
  50.  
  51. # --j=2--                                # --j=i--
  52. #   N     n                              #   N     n  
  53. #   5k   669   0.35s-7.9M                #   5k   669   0.28s-7.9M
  54. #  10k  1229   1.37s-7.9M  n^2.24        #  10k  1229   1.16s-7.9M  n^2.34
  55. #  20k  2262   5.21s-7.9M  n^2.19        #  20k  2262   4.66s-7.9M  n^2.28
  56. #  30k  3245  11.76s-7.9M  n^2.26        #  30k  3245  11.24s-7.9M  n^2.44
Success #stdin #stdout 11.24s 7852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3245
https://ideone.com/oq8mHy
http://stackoverflow.com/questions/21241858/sieve-of-eratosthenes-speed-differences
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

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!