# Sieve of Eratosthenes

Sieve of Eratosthenes is a simple and ancient algorithm used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers.

For a given upper limit \(n\) the algorithm works by iteratively marking the multiples of primes as composite, starting from 2. Once all multiples of 2 have been marked composite, the muliples of next prime, ie 3 are marked composite. This process continues until \(p\le \sqrt { n } \) where \(p\) is a prime number.

## Implementation

In the following algorithm, the number 0 represents a composite number.

- To find out all primes under \(n\), generate a list of all integers from 2 to n. (
**Note**: 1 is not prime) - Start with a smallest prime number, ie \(p = 2\).
- Mark all the multiples of \(p\) which are less than \(n\) as composite. To do this, mark the value of the numbers (multiples of \(p\)) in the generated list as 0.
**Do not**mark \(p\) itself as composite. - Assign the value of \(p\) to the next prime. The next prime is the next non-zero number in the list which is greater than p.
- Repeat the process until \(p\le \sqrt { n } \).

We are done!

Now all **non-zero** numbers in the list represent primes, while the numbers which are 0 in the list represent composite numbers.

## Example 1

Generate all the primes less than 11

First thing to note is that

do notmark prime themselves as composite.

- Create a list of integers from 2 to 10.
`list = [2, 3, 4, 5, 6, 7, 8, 9, 10]`

- Start with \(p=2\).
- Since \(2^2 \le 10\), continue.
- Mark all multiples of 2 as composite by setting their value as 0 in the list.
`list = [2, 3, 0, 5, 0, 7, 0, 9, 0]`

- Assign the value of \(p\) to the next prime, ie 3.
- Since \(3^2 \le 10\), continue.
- Mark all multiples of 3 as composite by setting their value as 0 in the list.
`list = [2, 3, 0, 5, 0, 7, 0, 0, 0]`

- Assign the value of \(p\) to 5.
- Since \(5^{ 2 }\nleq 10\), stop.
We are done!

The list is

`[2, 3, 0, 5, 0, 7, 0, 0, 0]`

. Since all the numbers which are 0 are composite, all the non-zero numbers are prime. Hence the prime numbers less 11 are 2, 3, 5, 7. \( _\square \)

## Example 2

Generate all the primes less than any integer \(n\)

Since \(n\) could be any large number, manually computing the answer would take years. Let's write a code for this.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24`import math n = 200 # n is any arbitrary integer List = [] for x in xrange(2, n): # add numbers from 2 to n - 1 to List List.append(x) # note the above statement is equivalent to List = range(2, n) p = 2 # p is a prime while not int(math.sqrt(p)) + 1 > n: # continue to mark out primes until square root of p is less than n for x in xrange(p * 2, n, p): # remove all the multiples of p List[x - 2] = 0 p += 1 while p - 2 < len(List) and List[p - 2] == 0: # assign p to the next prime. Next prime is the next non zero number in the list p += 1 for x in List: # search for non zero or prime numbers in the list and print them if x != 0: print x`

Here is an optimized java version -

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37`final int lim = 200; // exclusive int n[] = new int[lim - 2]; //exclude 1 for(int i = 2; i <= lim - 1; i++) //initialize the array with integers from 2 to lim { if((i & 1) == 0) //evens are not primes f & 1 return 0 if f % 2 == 0 { n[i - 2] = 0; } else { n[i - 2] = i; } } n[0] = 2; int p = 3; //start with a prime. Since 2 is already eliminated, start with 3 while(p * p < lim) { for(int i = p * p; i < lim; i += p + p) //remvove multiples of prime. Start at p * p { n[i - 2] = 0; } while(n[(p += 2) - 2] == 0) //find next non zero number. This is guaranteed to be a prime. ; } for(int i = 0; i < lim - 2; i++) //print non zero numbers { if(n[i] != 0) { System.out.println(n[i]); } }`

Proof:To see why Sieve of Eratosthenes generates all the primesTo first understand why the sieve works, let's look into the definitions of prime decomposition and composite numbers.

Theorem 1Every integer which is

greater than1 can be expressed as product of primes.

Theorem 2If any integer \(n\) is composite, then \(n\) has a prime divisor less than or equal to \(\sqrt { n }\).

Since for any number \(n\) in the list, we are looking all prime numbers up to \(\sqrt { n }\), we are indeed separating all composite numbers. Hence Sieve of Eratosthenes generates all primes numbers less than the upper limit. \(_\square\)

**Cite as:**Sieve of Eratosthenes.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/sieve-of-eratosthenes/