Sieve of Eratosthenes Algorithm to find Prime Number

Sieve of Eratosthenes is a simple and ancient algorithm used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers.

For a given upper limit n the algorithm works by iteratively marking the multiples of primes as composite, starting from 2. Once all multiples of 2 have been marked composite, the multiples of next prime, i.e. 3 are marked composite. This process continues until p*p ≤ n where p is the current prime number.

Following is the algorithm of Sieve of Eratosthenes to find prime numbers.

1. To find out all primes under n, generate a list of all integers from 2 to n.

(Note: 1 is not a prime number)

2. Start with a smallest prime number, i.e. p = 2
3. Mark all the multiples of p which are less than n as composite. To do this, we will mark the number as 0. (Do not mark p itself as composite.)
4. Assign the value of p to the next non-zero number in the list which is greater than p.
5. Repeat the process until p*p ≤ n

---

Example: Generate all the primes up to 11

First thing to note is that do not mark prime themselves as composite.
1. Create a list of integers from 2 to 11.

2	3	4	5	6	7	8	9	10	11

2. Start with p=2
3. Since 2*2 ≤ 11, continue.
4. Mark all multiples of 2 as composite by setting their value as 0 in the list.

2	3	0	5	0	7	0	9	0	11

5. Assign the value of p to the next prime, i.e. 3
6. Since 3*3 ≤ 11 , continue.
7. Mark all multiples of 3 as composite by setting their value as 0 in the list.

2	3	0	5	0	7	0	0	0	11

8. Assign the value of p to 5
9. Since 5*5 ≰ 11 so we stop here.
We are done! The list is:

2	3	0	5	0	7	0	0	0	11

Since all the numbers which are 0 are composite, all the non-zero numbers are prime.

Hence the prime numbers up to 11 are 2, 3, 5, 7, 11
 

Python program to print all primes smaller than or equal to a given limit using Sieve of Eratosthenes.

n = int(input("Enter an integer number:"))
prime = [] # An empty list
for i in range(n+1):
    prime.append(i)

prime[0]=0
prime[1]=0   

p = 2
while (p * p <= n): 
    # If prime[p] is not changed, then it is a prime 
    if (p != 0): 
        # Update all multiples of p to zero
        for i in range(p*2, n+1, p): 
            prime[i] = 0

    p += 1

#print all element of list which are not zero
print("All the prime numbers up to", n, "are:")
for i in range(len(prime)):
    if (prime[i] != 0):
        print(prime[i], end=" ")

OUTPUT:
Enter an integer number:30
All the prime numbers up to 30 are:
2 3 5 7 11 13 17 19 23 29