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

```
# 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)
break
else:
print(num, "is a prime number")
# if input number is less than 20
# or equal to 1, it is not prime else:
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 */
#include<stdio.h>
#include<math.h>
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 )
{
break;
}
}
if (i <= sq)
return 0;
else
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.