Day 05 - Sieve of Eratosthenes


Definition(s)

The sieve of Eratosthenes can be expressed in pseudocode, as follows:

 Input: an integer n > 1.

 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.

 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
       A[j] := false.

 Output: all i such that A[i] is true.

Algorithm(s)


In [1]:
import numpy as np

In [24]:
def sieve(n):
    assert n > 1
    A = np.ones(n + 1, dtype=np.int8)
    A[0] = A[1] = 0
    
    i = 2
    while i * i <= n:
        A[i * i::i] = 0
        i += 1
    
    return A

In [18]:
def primes(n):
    sv = sieve(n)
    return [x for x in range(n + 1) if sv[x]]

def is_prime(n):
    return sieve(n)[n]

Run(s)


In [25]:
n = 100
print("There are {0} primes less than {1}".format(sieve(n).sum(), n))


There are 25 primes less than 100

In [32]:
n = 10 ** 6
print("There are {0} primes less than {1}".format(sieve(n).sum(), n))


There are 78498 primes less than 1000000

In [26]:
n = 10 ** 8
print("There are {0} primes less than {1}".format(sieve(n).sum(), n))


There are 5761455 primes less than 100000000

In [30]:
n = 10 ** 9
print("There are {0} primes less than {1}".format(sieve(n).sum(), n))


There are 50847534 primes less than 1000000000

In [27]:
print(primes(100))


[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

In [29]:
print(is_prime(100))
print(is_prime(2853791))


0
1