# Sieve of Eratosthenes

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

1. Initialize an array of size N and fill it with 1. Let the name of the array be prime.
2. Set prime[1] = 0 since 1 is not prime.
3. Set p = 2.
4. 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.
5. 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.
6. 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

1. x is prime
If x is prime then we have already set . Since and . Thus, p*x is already set to 0.
2. 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