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