# 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 :

import numpy as np

``````
``````

In :

def sieve(n):
assert n > 1
A = np.ones(n + 1, dtype=np.int8)
A = A = 0

i = 2
while i * i <= n:
A[i * i::i] = 0
i += 1

return A

``````
``````

In :

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 :

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

``````
``````

There are 25 primes less than 100

``````
``````

In :

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

``````
``````

There are 78498 primes less than 1000000

``````
``````

In :

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

``````
``````

There are 5761455 primes less than 100000000

``````
``````

In :

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

``````
``````

There are 50847534 primes less than 1000000000

``````
``````

In :

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 :

print(is_prime(100))
print(is_prime(2853791))

``````
``````

0
1

``````