Sieve of Eratosthenes: Finding All Prime Numbers

Sieve of Eratosthenes

Problem Statement

Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

A prime number is a number that is divisible by only two numbers – themselves and 1

Example:

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

Input: n =10
Output: 2 3 5 7
Explanation: Only 4 prime numbers are there which are less than or equal to 10.

Finding Prime Numbers
Finding Prime Numbers

Input: n = 20 
Output: 2 3 5 7 11 13 17 19
Explanation: All above numbers are prime which are less than or equal to 20.


Simple Approach

Iterate from 2 to N, and check for prime. If it is a prime number, print the number.  Below is the implementation of the above approach

C++ Implementation

int checkPrime(int n) {
   if (n <= 1)
      return 0;

   for (int i = 2; i < n; i++)
      if (n % i == 0)
         return 0;

   return 1;
}
// Function to print all the prime numbers from 
// range 2 to n 
void printPrime(int n) {
   for (int i = 2; i <= n; i++) {
      if (checkPrime(i))
         cout << i << " ";
   }
}

Java Implementation

class Interviewbit {
   static int isPrime(int n) {
      for (int i = 2; i < n; i++)
         if (n % i == 0)
            return 0;

      return 1;
   }

   static void printPrime(int n) {
      for (int i = 2; i <= n; i++) {
         if (isPrime(i))
            System.out.print(i + " ");
      }
   }
}

Python Implementation

 def isPrime(n):
     
    # Corner case
    if n <= 1 :
        return False
 
    # check from 2 to n-1
    for i in range(2, n):
        if n % i == 0:
            return False
 
    return True
 
# Function to print primes
def printPrime(n):
    for i in range(2, n + 1):
        if isPrime(i):
            print(i, end = " ")

Time complexity: O(N*N), Where N is the number.
Space complexity: O(1)


Efficient Approach: Sieve of Eratosthenes

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method: 

When the algorithm terminates, all the numbers in the list that are not marked are prime. 

  • Firstly write all the numbers from  2,3,4…. n
  • Now take the first prime number and mark all its multiples as visited.
  • Now when you move forward take another number which is unvisited yet and then follow the same step-2 with that number.
  • All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.

Dry run of the above approach

Step 1: The numbers between 1 and 100 are listed in the table below.

12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100

Step 2: The next step is to write in bold all the multiples of 2, except 2 itself.

12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100

Step 3: Now bold all multiples of 3, 5, and 7 and only leave these numbers.

12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100

Step 4: Since the multiples of 11, 13, 17, and 19 are not present on the list, 1 is finally shaded because it is not prime.

12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51525354555657585960
61626364656667686970
71727374757677787980
81828384858687888990
919293949596979899100

Step 5: The unshaded numbers are prime. They include:

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

C++ Implementation Efficient Approach

void SieveOfEratosthenes(int n)
{
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            cout << p << " ";
}

Java Implementation of Efficient Approach

class SieveOfEratosthenes {
	void sieveOfEratosthenes(int n)
	{
		boolean prime[] = new boolean[n + 1];
		for (int i = 0; i <= n; i++)
			prime[i] = true;

		for (int p = 2; p * p <= n; p++){
			if (prime[p] == true)
			{
				for (int i = p * p; i <= n; i += p)
					prime[i] = false;
			}
		}

		for (int i = 2; i <= n; i++)
		{
			if (prime[i] == true)
				System.out.print(i + " ");
		}
	}
}

Python Implementation of Efficient Approach

 def SieveOfEratosthenes(n):
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        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+1):
        if prime[p]:
            print p,

Time complexity of Sieve of Eratosthenes:

Space complexity: O(1)

Analysis of Time Complexity

  • PREREQUISITE: Time complexity of the Harmonic Series is O(logN), when N is tending to infinity.
  • If we analyze our sieve for larger numbers then we can see .
    • The inner loop at each iteration can be expressed by:
    • i=2, the inner loop will be executed → upper bound is (n/2) times
    • i=3, the inner loop will be executed → upper bound is (n/3) times
    • i=5, the inner loop will be executed → upper bound is (n/5) times
    • i=n(if prime number), the inner loop will be executed → upper bound is 1 times.
  • The above series time complexity is less than harmonic series: 
    • n/2 + n/4 + ..+ 1 → n (1/2 + 1/3 + 1/4 + … 1/n), 
  • Hence, the run loop times should be 
    • n (1/2 + 1/3 + 1/5 + 1/7 + 1/ 11 + 1/13 + …).= logn That is why, in some article, 
  • The time complexity is defined in O(nloglogn).

Conclusion

The outer loop is a general for-loop from 1 to N, the time complexity is O(N). The total time complexity is O(NloglogN).


Practice Questions


Frequently Asked Questions

Q: How fast is Sieve of Eratosthenes?
A: It is very fast as it can store prime numbers up to the 1e7 range easily.

Q: How do you improve the sieve of Eratosthenes?
A: We can further improve the sieve to O(n) by writing it to an iterative sieve.

Q: How does the Sieve of Eratosthenes work?
A: It works on the principle of cancellation of prime factors.

Previous Post
GCD of Two Numbers

GCD of Two Numbers (C, Python, Java) With Examples

Next Post
Preorder Traversal

Preorder Traversal

Total
0
Share