Sieve Of Eratosthenes | Mathematics | Data Structures and Algorithm | Python

Problem Statement:

The Sieve of Eratosthenes is a method for finding all primes up to (and possibly including) a given natural n$n\text{.}$ This method works well when n$n$ is relatively small, allowing us to determine whether any natural number less than or equal to $n$ is prime or composite.

Explanation:

Suppose n = 100

Step 1: A/c to the algorithm we will mark all the numbers which are divisible by 2 and are greater than or equal to the square of it.

Step 2: Now move to next unmarked number 3 and mark all the numbers which are multiple of 3 and are greater than the square of it.

Now move to next unmarked number 5 and mark all the numbers which are multiple of 5 and are greater than the square of it.

Now move to next unmarked number 5 and mark all the numbers which are multiple of 5 and are greater than the square of it.

Now we have reached the limit. All the unmarked numbers are prime numbers.

So the list of prime numbers are:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Code: 

See you in the next article.

Until Then...

Byeeee

Facebook Google Twitter More

• Pinterest
• Linkedin
• Tumblr

April 03, 2022

Subscribe by Email

Follow Updates Articles from This Blog via Email