What is the Sieve Method?

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.

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

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)
                break;
                else
                primes[primes[i]*j]=0;    // Instead of deleteing, making elements 0
            }
        }
        i++;
    }

    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;
}

You can also try this code with Online C Compiler

Run Code

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:

             Image Source: Euler’s totient function – Competitive Programming Algorithms (cp-algorithms.com)

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.

                                                                Image source: (blog.naver.com)

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)).

Algorithm

• 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;
}

You can also try this code with Online C++ Compiler

Run Code

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.io.*;
import java.util.*;
import java.math.*;

public class Main { 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        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");
            }
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

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.

Conclusion

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!