fork(1) download 
  1. # Sieve of Eratosthenes prime number generation. (3.00)
  2.  
  3. def isprime(n):
  4.     for i in range(2, n):
  5.         if n % i == 0:
  6.             return False
  7.     return n > 1
  8.  
  9. def prime_expect(n):
  10.     return [i for i in range(n+1) if isprime(i)]
  11.  
  12. def sieve_1(n):
  13.     n = max(1, n)
  14.     a = [1] * (n-1)
  15.     i = 2
  16.     while i*i <= n:
  17.         if a[i-2] != 0:
  18.             a[i*i-2::i] = [0] * (n//i-i+1)
  19.         i += 1
  20.     return [i for i, v in enumerate(a, 2) if v]
  21.  
  22. def sieve_2(n):
  23.     n = max(1, n)
  24.     a = [1] * (n-1)
  25.     u = 101
  26.     i = 2
  27.     while i*i <= n:
  28.         # Unguarded.
  29.         a[i*i-2::i] = [0] * (n//i-i+1)
  30.         # Generate integer sequence (repeating decimal).
  31.         # 101/825 = 0.1224..24
  32.         d, u = divmod(u * 10, 825)
  33.         i += d
  34.     return [i for i, v in enumerate(a, 2) if v]
  35.  
  36. def sieve_3(n):
  37.     n = max(1, n)
  38.     # Optimize for size (use bytearray).
  39.     a = bytearray(b'\1' * (n-1))
  40.     u = 101
  41.     i = 2
  42.     while i*i <= n:
  43.         # Unguarded.
  44.         a[i*i-2::i] = b'\0' * (n//i-i+1)
  45.         # Generate integer sequence (repeating decimal).
  46.         # 101/825 = 0.1224..24
  47.         d, u = divmod(u * 10, 825)
  48.         i += d
  49.     return [i for i, v in enumerate(a, 2) if v]
  50.  
  51. def sieve_4(n):
  52.     if n < 2:
  53.         return []
  54.     # Optimize for size (implicit twos; use bytearray).
  55.     m = (n-1)//2
  56.     a = bytearray(b'\1' * m)
  57.     u = 37
  58.     i = 3
  59.     while i*i <= n:
  60.         # Unguarded.
  61.         a[i*i//2-1::i] = b'\0' * ((m-i*i//2) // i+1)
  62.         # Generate integer sequence (repeating decimal).
  63.         # 37/165 = 0.224..24
  64.         d, u = divmod(u * 10, 165)
  65.         i += d
  66.     return [2] + [2*i+1 for i, v in enumerate(a, 1) if v]
  67.  
  68. # Test.
  69.  
  70. from time import process_time
  71.  
  72. def _test(n, f):
  73.     print(f.__name__)
  74.     for i in range(258):
  75.         assert f(i) == prime_expect(i)
  76.     t = process_time()
  77.     for i in range(n):
  78.         f(2**i-1)
  79.     t = process_time() - t
  80.     print(f'Elapsed: {t:.9f}s')
  81.  
  82. n = 43
  83. print(prime_expect(n))
  84.  
  85. n = 20
  86. _test(n, sieve_1)
  87. _test(n, sieve_2)
  88. _test(n, sieve_3)
  89. _test(n, sieve_4)
Success #stdin #stdout 0.38s 18980KB
comments (?)
stdin 
Standard input is empty
stdout 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
sieve_1
Elapsed: 0.098275157s
sieve_2
Elapsed: 0.097672450s
sieve_3
Elapsed: 0.092358420s
sieve_4
Elapsed: 0.058782549s
https://ideone.com/qYZ1rG
language:
Python 3 (python  3.12)
created:
2 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!