Sieve of Eratosthenes

Finding All Prime Numbers

Problem Statement

For a given number n, print all primes <= n. Also, n is a small number. Prime numbers are only divisible by themselves and 1.

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

Example:

Simple Approach

1. Iterate from 2 to N.  2. Check for prime numbers.  3. Print the number if it is a prime number.

Time complexity: O(N*N) Here, N = number Space complexity: O(1)

1. Write all the numbers from 2,3,4…n.  2. Take 1st prime number and mark all of its multiples as visited.

Efficient Approach: Sieve of Eratosthenes

3. Now, take the next unvisited number and follow step 2 with that number.  4. Numbers that remain unmarked at the end of the algorithm are prime numbers.

Time Complexity: O(N *(log(log(N))))  Space complexity: O(1)

How to implement the solution in different languages?