Sieve? **What** is Sieve? And **why** we need that? 🤷

## PROBLEM STATEMENT

👉 Let’s start with the reason to understand Sieve 📃

So the problem is ➡️ We have a **number “n”** and we have to find all the prime numbers **less than or equal to “n”**.

## Naive Approach

😎 *Basic approach* would be just running a **loop form 1 to n **and check all the numbers individually💩

BUT WAIT 🤚

**Is this a good solution**❓️ Obviously it isn’t! I mean let’s say “**n”** is very large, then it’s going to take a hell **lot of time**⏳️

**Now the real question** is how to find the solution in less time 🤔

** And here the idea of Sieve comes** 💡 But before discussing that let’s play with some numbers and see if we find something interesting 😋

## Understanding Through Example

Let’s take an example… **n = 10, 25, 36, 50, 37**

**10** = 1*10 = 2*5 = **Root(10) ≈ 3**

**25** = 1*25 = 5*5 = **Root(25) = 5**

**36** = 1*36 = ** **2*18 = ** **3*12 = 4*9 = 6*6 = **Root(36) = 6**

**50** = 1*50 = 2*25 = 5*10 = **Root(50) ≈ 7**

**37** = 1*37 ** = Root(37) ≈ 6**

**HEY ! **Did you saw something Interesting? 😃

👀 Observe the numbers carefully **if it is non-prime it will have at least one divisor less than or equal to its root**.

Let me explain above line in better way 😇 👇

**Let’s see this **👉 36 =** 1***36 **2 ***18 **3***12 **4***9 **6***6 Root(36) =** 6**

**1***36 ➡️ we have**1**which is*less than or Equal*to root (6)

**2***18 ➡️ we have**2**which is*less than or Equal*to root (6)

**3***12 ➡️ we have**3**which is*less than or Equal*to root (6)

**4***9 ➡️ we have**4**which is*less than or Equal*to root (6)

**6***6 ➡️ we have**6**which is*less than or Equal*to root (6)

*Wohoo*🎉 Now rather than checking Prime Number by divisibility from **2 to n,** we can simply check divisibility from** 2 to root(n)** .

**In other words**, *36’s root is 6* So, can we have **A x B = 36** where A and B **both are greater than 6**? 🤔 Obviously not ! That’s why it makes sense to only check divisibility from** 2 to root(n)** ✅️

## Now comes sieve, Let’s see how it works!

▶️ Suppose, we have a number **’20**‘, What we can do is to make a table from **1 to 20**.

Let’s mark **Prime as green**🟢 & **Non-Prime as red**🔴

We will **start from 2** mark it green and mark **all its multiple** red. Now we will **pick up the next unmarked number** and do the same.

*20 will have at least one divisor less than or equal to its root*.

So any number **less than 20** will have at **least one divisor less than or equal to root(20)**. So it will be enough we continue the *marking process* *from 2 to root(20)* 👍

First, mark **1 as red**🔴 and **2 as green**🟢 all it’s **multiple** as red🔴

Now, take the **next unmarked number which 3 **mark as green🟢 and all **multiples** of it as red🔴

**Root(20) ≈ 4** as it is already marked * so all the unmarked numbers are prime*…mark them as green🟢

Now, notice one important thing here !

While marking **multiples for 3** : 6, 9, 12, 15

(*6 was already marked* by 2)

**Similarly**, we can say for every number we need to start marking it’s multiples(Red) from it’s **square**. ✔️

So suppose for ‘**4′,** we could have started marking multiples 🔴 from **16** 👉 **( 16, 20)** as for (**8, 12)** we can be assured that numbers before ‘4’ would have already marked them as Red ! (**2***4 = **8,** ** 2***6=**12**).

Three important observations are:

**While checking if number is prime iterate from 2 to Root(n)**☑️**While marking table for Sieve of Eratosthenes, only pick numbers up to Root(n)**☑️**While marking multiples of a number in Sieve of Eratosthenes, start picking multiples from it’s square (As multiples before square would already be marked)**☑️

## C++ Implementation – Sieve of Eratosthenes

**Arnabi Mitra**

System Engineer Specialist, InfosysThe best way to predict the future is to create it.

## 11 Comments

## Reshma Sharma · January 19, 2021 at 2:10 am

Really nice way of publishing blogs.

It never looks boring.

Thanks for the great info Arnabi !

## Arnabi Mitra · January 19, 2021 at 11:30 am

Thank you

## Saptarshi Banerjer · January 19, 2021 at 9:37 am

Very insightful writing

## Arnabi Mitra · January 19, 2021 at 11:31 am

😁

## Ankit Narang · January 19, 2021 at 12:27 pm

The way you presented the information is mind blowing Arnabi.

I would try to change my next Blog like yours. Thanks for the great idea ^

## Arnabi Mitra · January 19, 2021 at 1:18 pm

Thanks

## Shant_01 Ohlyan · January 21, 2021 at 12:14 pm

Nice structured blog and color combination is great to.

Keep it up.

## Shivam Singh · March 14, 2021 at 11:12 am

Hi Arnabi, you made the article look to easy yet too informative with great spark of placements and colors.

Thanks for this Blog !!

## Chinmay Bisht · May 2, 2021 at 10:12 pm

Th way you wrote it looks damn easy and clean.

Kudos to you Arnabi

## zortilo nrel · September 16, 2021 at 10:34 am

Hey There. I found your blog using msn. This is a really well written article. I’ll be sure to bookmark it and return to read more of your useful info. Thanks for the post. I’ll definitely return.

## Dhruv Bisht · January 29, 2022 at 3:22 pm

Hey Arnabi, this blog is cool, but I can’t find any other algo, DS concepts shared apart from Sieve. Please share graph based algo if possible