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🔴

sieve of eratosthenes C++
1 as Red, 2 as green with all it’s multiple as red.

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

sieve of eratosthenes C++
3 as Green and all it’s multiple Red

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

sieve of eratosthenes C++
Remaining numbers as Green – Reached Root(20)

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:

  1. While checking if number is prime iterate from 2 to Root(n) ☑️
  2. While marking table for Sieve of Eratosthenes, only pick numbers up to Root(n) ☑️
  3. 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

sieve of eratosthenes C++

Arnabi Mitra

System Engineer Specialist, Infosys

The best way to predict the future is to create it.

Don’t forget to visit 😃👇

Want your own Blog ? 🤩

Inclined Scorpio helps to bring up your own content and design it your way with perfect finish ! ⚡️

Just in case, you missed the details, email 📩ashutoshtiwari3309@gmail.com for details.


8 Comments

Avatar

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 !

    Avatar

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

    Thank you

Avatar

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

Very insightful writing

    Avatar

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

    😁

Avatar

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 ^

Avatar

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

Thanks

Avatar

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

Nice structured blog and color combination is great to.
Keep it up.

Avatar

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 !!

Leave a Reply

Your email address will not be published. Required fields are marked *