What is the Sieve Method?

Introduction

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.

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:

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?

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

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.

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

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 factorisation 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:

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.

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:

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:

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.

By Yogesh Kumar