Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
What is the Sieve of Eratosthenes?
Working of Sieve of Eratosthenes
Euler’s Phi / Euler’s Totient Function using Sieve
Sum of Divisors Sieve 
Frequently Asked Questions
What is sieve theory?
What is Euler’s totient function?
What is the main use of the Sieve of Eratosthenes?
Last Updated: Mar 27, 2024

What is the Sieve Method?

Master Python: Predicting weather forecasts
Ashwin Goyal
Product Manager @


Sieve theory is a set of one of the general techniques used in number theory. It helps in counting, or to get an estimation of the size of the sifted sets of integers.

Introduction to sieve method.

According to Wikipedia, the Sieve method, or the method of sieves, has the following meanings:

  • In mathematics and computer science, the sieve of Eratosthenes, a simple method for finding prime numbers.
  • In number theory, any of a variety of methods studied in sieve theory.
  • In combinatorics, the set of methods dealt with in sieve theory or more specifically, the inclusion-exclusion principle.
  • In statistics, and particularly econometrics, the use of sieve estimators.

The prototypical example of a sifted set is the collection of prime numbers up to some prescribed limit X. In the same order, the prototypical example of a sieve is the sieve of Eratosthenes.

Let’s first start by seeing the Sieve Method for prime no. or should I say Sieve of Eratosthenes. Let’s try to understand this with an example, Suppose if you want to find if a number is prime or not then how will you do it? Let’s try with a noob’s approach:

Python implementation for the same:

# Program to check if a number is prime or not
num = 527
# To take input from the user
#num = int(input("Enter a number: "))

# prime numbers are greater than 1
if num > 1:
   # check for factors 
  for i in range(2,num): 
      if (num % i) == 0:
          print(num, "is not a prime number") 
          print(i,"times", num//i,"is", num)
       print(num, "is a prime number")
# if input number is less than 20 
# or equal to 1, it is not prime else:
 print(num, "is not a prime number")

But trust me that’s the worst solution you’ll find on the internet because you’re doing nothing it’s just a brute force approach in which you’re checking for every number between 2 to n and if n is divisible by any number in-between then simply it’s not a prime number. So if you think this approach will work in competitive programming then I feel really sorry for you it wouldn’t ever.

Another better approach to the problem? Of course, you can do one thing, instead of iterating the loop from 2 to n, you can iterate it up to the square root of N. But why? Because remember one thing that smallest and greater than one factor of a number cannot be more than the sqrt of N. And we will stop where we find the factor. Makes sense right?

/*Function to find prime number if so return 1 else return */

int isprime( int num)
	int i;
	int sq = (int) sqrt (num);
	/* here check should be done for num = 0 and 1 other wise 0 and 1 are printed as 
	primes */
	/* if (num <= 1) return 0; */
	for (i=2; i <= sq; i++)
		if (num % i == 0 )
	if (i <= sq)
  	  return 0;
  	  return 1;


But here we can see that the above algorithm is performing well at least we are not iterating till n. But if we talk about competitive programming then there could be a possibility that our above-optimized algorithm might not be able to perform well.

But we will try to optimize it more with time complexity of O (n logn) and this method is also known as Sieve of Eratosthenes. Well, don’t scare me from the name it’s an ancient algorithm. Let’s try to understand it in simple words.

What is the Sieve of Eratosthenes?

Consider an example and nature lover will get it soon. Kidding! Imagine you’re in the middle of a forest and you listen to the sound of the waterfall and you go near it and find a river and you’re thirsty and want to drink water. You pour the water into your bottle but realize it has small pebbles you can’t remove with your hands then you realize you’re carrying a sieve in your bag so you could separate the water from pebbles. What do you do?

You take a sieve, pour the water (with the pebbles in it) from one side, and the clear water comes out from the other. Now you have separated the pebbles and the water and can use each for whatever purpose you want to.

Now imagine the water to be all the natural numbers and imagine the pebbles to be the prime numbers and now consider we are pouring the natural numbers (“water”) from one side and the prime numbers (“pebbles”) are leftover on the sieve. That’s why sieve is called the ‘Sieve of Eratosthenes’.

As we know a prime number is a whole number that has exactly two factors, 1 and itself. The Sieve of Eratosthenes is an ancient algorithm with which you can find all prime numbers up to any given limit.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Working of Sieve of Eratosthenes

Let’s see if we have to find all prime numbers that are less than 100 then:

  • Step 1: Write all the numbers from 1 to 100 in ten rows."
  • Step 2: Marks cross to 1 because 1 is not a prime number.
  • Step 3:: Circle 2 and cross all the multiples of 2 {2, 4, 6, 8, 10, …..}
  • Step 4: Circle 3 and cross all the multiples of 3. (3, 6, 9, 12, 15, …)
  • Step 5: Circle 5 and cross all the multiples of 5. (5, 10, 15, 20, …)
  • Step 6: Circle 7 and cross all the multiples of 7. (7, 14, 21, 28, …)

We will repeat the above steps till 100 basically we have to circle all the numbers that are not crossed out and they are the prime numbers less than 100.

prime numbers less than 100.

 primenumbrs-grid-1.jpg (532×414) (

So the intuition behind the algorithm is clear now let’s try to find out how to implement the algorithm in C:

#include <stdio.h> 
int main()
    int number,i,j;
    printf("Enter the number\n"); 
    scanf("%d", &number);
    int primes[number+1];

    for (i=2; i<=number; i++) 
        primes[i] = i;   //populating array with naturals numbers
    i = 2;

    while ((i*i) <= number)
        if (primes[i] != 0)
            for(j=2; j<number; j++)
                if (primes[i]*j > number)
                primes[primes[i]*j]=0;    // Instead of deleteing, making elements 0

    for (i= 2; i<=number; i++)
        if (primes[i]!=0) //If number is not 0 then it is prime
            printf("%d\n", primes[i]);
    return 0;

The time complexity of the above algorithms is O (n*log n).

Euler’s Phi / Euler’s Totient Function using Sieve

As we know Number theory is one of the important topics in the field of Math and Competitive Programming. Many times a coder or I should say a competitive programmer especially if we talk in computer science must have come across problems that relate to the prime factorization of a number, to the divisors of a number, to the multiples of a number and so on.

Basically, if we want to get the exact meaning or use of Euler’s totient function is, it is a function that is related to getting the numbers of number that are coprime to a certain number X which are less than or equal to it. In short, If we talk about number X now find the count of all numbers Y where the greatest common divisor i.e. gcd (X, Y) = 1 and 1 <=Y <= X.

Here are values of ϕ(n)ϕ(n) for the first few positive integers:

values of ϕ(n)ϕ(n) for the first few positive integers

             Image Source: Euler’s totient function – Competitive Programming Algorithms (

In one-word Totient function helps in counting the number of co-prime numbers of a number. To calculate that, we could iterate from all numbers from 1 to n and check if gcd(n,x) = 1. But we don’t need to do that. But that would be hectic and would also be a naïve approach. Instead of this, calculate all prime numbers (p) smaller or equal to n and use Euler’s product formula.

The formula clearly states that the value of n is equal to n multiplied by the product of (1 – 1/p) for all prime factors p of n. For example value of ?(6) = 6 * (1-1/2) * (1 – 1/3) = 2.

formula used in evaluating (6) = 6 * (1-1/2) * (1 – 1/3)

                                                                Image source: (

formula  for all prime factors p of n

For finding the prime numbers, we have to iterate from 2 to sqrt(N). Therefore, the overall time complexity of the function is O(sqrt(N)).


  • We will initialize a variable result = n
  • Run a loop from ‘i’ = 2 to sqrt(n), and do the following thing for ‘i’.
    • If I divide n, then
    • Set: result = result  * (1.0 – (1.0 / (double) i));
    • Then Divide all occurrences of i in n.
  • Finally, the Return result

Below is a C++ implementation of the function:

int totient(int n){
    double result = n;
    //"calculate" prime numbers up to n
    for(int i=2;i*i<=n; i++){
        // if n% i == 0, then i is a prime number
        if(n % i == 0){
            while(n % i == 0) n /= i;
            // Euler's Formula
            result *= (1.0 - (1.0/(double)i));
    // if n is different from 1, then it is also prime
    if(n != 1) 
    	result *= (1.0 - (1.0/(double)n));
    return (int)result;

Sum of Divisors Sieve 

With the help of the sieve method, we can find the no. of divisors of numbers up to N. But here we will see that how can sieve method helps in finding the sum of divisors.

Let’s say if we want to find the number of divisors of a number. From above things, it is clear that One way is to check all numbers up to √n and check if n divides that number. Another way could be to find its prime factorisation and get the product of (exponent + 1) through combinatorics.

Now think of the same case if you’re doing competitive programming (print the number of divisors of all numbers from 1 to 10^7 under 3 seconds? ) then would the above method will help? God knows! So don’t rely on it instead of let’s think of optimizing it. An O(n√n) algorithm will be too slow!

Fortunately, we have the Sieve of Eratosthenes method which can help in counting the number of divisors more efficiently. And eventually, you will get to know that this technique not only works for finding a number of divisors but also for generating some divisors, totient function, biggest prime divisor, basically all functions that have to do with divisors!

Now think of another problem we will solve below, you’re supposed to find the sum of divisors of all numbers up to N. Let’s see how will we implement the algorithm. Here let us declare a variable named divisorSum and consider divisorSum[i] denotes the sum of divisors of i. Initially, the value of divisorSum[i] is equal to zero. Iterate I from 1 to n for all numbers, We have to check all the multiples of i (let us say j) and then add i to divisorSum[j].

In other words, Start iterating from 1 and for all the numbers which are multiples of 1, increase their sumDiviors by 1.

Now do the same for 2,3, … N. Keep in mind that for number i, you have to do this adding operation upto N/i times. So the complexity calculation is the same as before. Let’s try to understand it with the example of a problem. Suppose you have to find the sum of divisors of all divisors of a natural number then how will you do.

Consider n = 54, then it’s divisors are= 1, 2, 3, 6, 9, 18, 27, 54 and then sum of divisors of each divisor of 54. Sounds confusing right? Don’t worry First of all we’re supposed to find the divisor of n and then we have to find all divisors for each divisor of 54 like 1 which has only 1 divisor so it’s sum is 1 , 2 it’s divisors are 1,2 so sum is 3, 3 it’s divisors are 1,3 so it’s sum is 4, 6 it’s divisors are 1,2,3,6 so it’s sum is 12 and so on. So sum of divisors of 1,2,3,6,9,18,27,54 are 1, 3, 4, 12, 13, 39, 40, 120 respectively.

So finally sum of divisors of all divisors of 54 = 1 + 3 + 4 + 12 + 13 + 39 + 40 + 120 = 232.

Here is the code for the same in Java:

import java.util.*;
import java.math.*;

public class Main { 
    public static void main(String[] args) {
        Scanner sc = new Scanner(; 
        int T = sc.nextInt();
        for (int t=0;t<T;t++) {
            int n = sc.nextInt();
            int divisorSum[] = new int [n + 1];
            //For every number 1, You know that 2*i,3*i,4*i upto k*i such that k*i<=n.
            // as one of it's divisors, so add that to divisorSum[j]
            for (int i = 1; i<=n; i++){
                for (int j = i; j<=n; j+=i){
                    divisorSum[j] += i;
            // Complexity of this code is 0(n * logn)
            // Proof: Expression for the complexity can be written as n / 1 + n / 2 + ..... 
            // take n common 
            //n* (1 + 1 / 2 + ...... + 1/n)
            // (1 + 1 / 2 + 1 / 3 + .... + 1 / n) is harmonic sum and it's bounded by logn.
            // A simple Proof: Let us integrate 1 / x from 1 to n.
            //Note that we are doing integration, which means sum of area under the curve 1/x
            // which is greater than (1 + 1 / 2 * ... + 1 / n)
            // value of interation can be found easily
            // as interration of 1/x dx is ln(x)

            for (int i = 1; i<=n; i++)
                System.out.printf("%d ", divisorSum[i]);
                System.out.printf ("\n");

Frequently Asked Questions

What is sieve theory?

Sieve theory is a set of one of general techniques used in number theory. It helps in counting or to get an estimation of the size of the sifted sets of integers.

What is Euler’s totient function?

Euler’s totient function is a function that is related to getting the numbers of number that are coprime to a certain number X which are less than or equal to it.

What is the main use of the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm with which you can find all prime numbers and composite numbers up to any given limit.


This Sieve method is one of the most important methods in number theory which is widely used in Competitive Programming with which you can find a prime number, divisors of a number with an optimized solution.

Not only this there’s another algorithm known as Segmented Sieve with which you can optimise Simple Sieve of Eratosthenes. We’ll talk about segmented sieve on some other day but if you’re really curious then you can surely understand the Segmented Sieve method from the Coding Ninjas YouTube page.
You can also consider our Competitive Programming Course to give your career an edge over others!
Happy Coding!

Previous article
All Possible Walks from a Source to a Destination with exactly k Edges
Next article
Channel Assignment Problem
Live masterclass