Sieve of Eratosthenes is an ancient algorithm that is used to find prime numbers up to a given limit.

## How it works?

Let N be the number up to which we want to find prime numbers. The algorithm creates an array of size N such that if the ith index of the array is 1 then i is prime and if the ith index of the array is 0, then i is not prime.

## Steps to Implement Sieve of Eratosthenes

- Initialize an array of size N and fill it with 1. Let the name of the array be prime.
- Set prime[1] = 0 since 1 is not prime.
- Set p = 2.
- If prime[p] is equal to 1 then it means no number less than p divides p, thus p is a prime number. Set all prime[j] = 0 | j is a multiple of p in range [p*p, n], j = p*p, p*p + p, p*p + 2p, p*p + 3p, … and so on.
- If prime[p] is equal to 0, then it means there exists a number less than p that divides p. Thus, p is not prime. Do nothing.
- Increment p. If p <= sqrt(N), then go back to step 4.

Basically, we loop through every number from 2 to sqrt(N) and check if that number is prime or not. If the numbers is prime ( prime[p] == 1 ) then we set all multiples of that number to not prime ( prime[j] = 0 ). Since prime numbers are not divisible by any number, their index value prime[p] remains 1.

**In step 3, you may be wondering why we only set multiples of p in the range [p*p, n] to 0 and not from [p*2, n]? **

This is because multiples of p less than p*p are already set to 0. Suppose p*x | x < p, We have 2 cases – x is prime and x is not prime

**x is prime**If x is prime then we have already set . Since and . Thus, p*x is already set to 0.**x is not prime**

If x is not prime, then prime[x] = 0. Therefore, there . This implies x is a multiple of y. Therefore, p*x is a multiple of y. All multiples of y are already set to 0. Thus, p*x is already 0.

**You may have noticed that the value of p ranges [2, sqrt(N)]**. This is because if then . The array index goes out of bound.

## Step by Step Example of Sieve of Eratosthenes

Suppose you want to find all prime numbers up to 64. First, create a list named prime of size 64 and fill it with 1. Set prime[1] to 0 since 1 is not a prime.

Set p = 2.

Check if p is prime or not. prime[2] == 1, thus 2 is prime. Set all multiples of 2 in the range [2*2, 64] to 0.

Move to next p | prime[p] = 1. The next number is p = 3. Set all multiples of 3 in range [3*3, 64] to 0.

Move to next p | prime[p] = 1. The next number is p = 5. Set all multiples of 5 in range [5*5, 64] to 0.

Move to next p | prime[p] = 1. The next number is p = 7. Set all multiples of 7 in range [7*7, 64] to 0.

The next p | prime[p] = 1 is 11. But the upper limit of p is sqrt(64) = 8. Thus, we terminate the loop.

A number p is prime if prime[p] = 1. Prime numbers up to 64 are : 2, 3, 5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61.

## Pseudo Code

```
algorithm sieve_of_eratosthenes( N )
Initialize a list prime of length N
Fill prime with 1
for p = 0 to p = square_root(N) do
if prime[p] = 1
set all multiples of p in range [p*p, n] to 0
set j = p*p
while j < n do
set prime[j] = 0
set j = j + p
end while
end if
end for
return prime
end
```

## Program in C/C++

```
#include<stdio.h>
#include<math.h>
#include<string.h>
int prime[100000];
void SieveOfEratosthenes(int n){
int p,j;
// set all elements of prime[] to 1
for(j=0;j<=n;++j)
prime[j] = 1;
prime[1] = 0; // 1 is not prime
for(p=2;p<=sqrt(n);++p){
for(j=p*p;j<=n;j+=p){
prime[j] = 0;
}
}
}
int main() {
int i,n;
printf("Enter Number: ");
scanf("%d",&n);
SieveOfEratosthenes(n);
printf("\nAll Prime Numbers up to %d are: \n",n);
for(i=1;i<=n;++i){
if(prime[i])
printf("%d\n",i);
}
}
```

**Output**

Enter Number: 64 All Prime Numbers up to 64 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61

**References**

Sieve of Eratosthenes