SIEVE OF ERATOSTHENES

Sieve of Eratosthenes:

Sieve of Eratosthenes is used to get all prime number in a given range and is a very efficient algorithm. 

Following is the algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p2, count up in increments of p and mark each of these numbers greater than or equal to p2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc..
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

Explanation with Example:
Let us take an example when n = 50. So we need to print all print numbers smaller than or equal to 50.

We create a list of all numbers from 2 to 50.

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

Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3 and are greater than or equal to the square of it.

We move to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal to the square of it.

We continue this process and our final table will look like below:

So the prime numbers are the unmarked ones: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

BELOW IS THE PROGRAM OF THE ALGORITHM::

# Python program to print all primes smaller than or equal to 

# n using Sieve of Eratosthenes 

def SieveOfEratosthenes(n): 

# Create a boolean array "prime[0..n]" and initialize 

# all entries it as true. A value in prime[i] will 

# finally be false if i is Not a prime, else true. 

prime = [True for i in range(n+1)] 

p = 2

while (p * p <= n): 

         # If prime[p] is not changed, then it is a prime 

if (prime[p] == True): 

# Update all multiples of p 

for i in range(p * p, n+1, p): 

prime[i] = False

p += 1

# Print all prime numbers 

for p in range(2, n): 

if prime[p]: 

print p, 

# driver program 

if __name__=='__main__': 

n = 30

print "Following are the prime numbers smaller", 

print "than or equal to", n 

SieveOfEratosthenes(n) 

Output:

Following are the prime numbers below 30

2 3 5 7 11 13 17 19 23 29

The sieve of Eratosthenes can be expressed in pseudocode, as follows:

 Input: an integer n > 1.

 
 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
       A[j] := false.
 
 Output: all i such that A[i] is true.

TO BE MORE CLEAR ABOUT THIS ALGO REFER THE LINK OF 1 MIN VIDEO:
https://youtu.be/ATyAnOCI1Ms