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