Sieve of Eratosthenes Algorithm

Problem

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

Examples

Example 1:

Input: n = 10
Output: [2, 3, 5, 7]

Example 2:

Input: n = 20
Output: [2, 3, 5, 7, 11, 13, 17, 19]

The sieve of Eratosthenes is highly efficient for finding all prime numbers less than n, particularly when n is below approximately 10 million (Wiki).

Solution

Algorithm

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

Create a List:
- Create a boolean array isPrime[] and initialize all entries as true. A value in isPrime[i] will be false if i is not a prime, otherwise true.
Mark Non-Primes:
- Start with the first prime number, p = 2.
- Mark all multiples of p as not prime.
- Move to the next number. If it is unmarked (still true), it is a prime number.
- Repeat the process until p^2 is greater than n.

Dry Run

Let us take an example when n = 48. So we need to return all prime numbers smaller than or equal to 24.

We create a boolean array or 48 element, initially, all values are true. $$ \begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 & 26 & 27 \\ 28 & 29 & 30 & 31 & 32 & 33 & 34 \\ 35 & 36 & 37 & 38 & 39 & 40 & 41 \\ 42 & 43 & 44 & 45 & 46 & 47 & 48 \\ \end{matrix} $$ Now, As per the algorithm, we will mark all numbers that are divisible by 2 (say with red) $$ \begin{matrix} 0 & 1 & 2 & 3 & \colorbox{red}{4} & 5 & \colorbox{red}{6} \\ 7 & \colorbox{red}{8} & 9 & \colorbox{red}{10} & 11 & \colorbox{red}{12} & 13 \\ \colorbox{red}{14} & 15 & \colorbox{red}{16} & 17 & \colorbox{red}{18} & 19 & \colorbox{red}{20} \\ 21 & \colorbox{red}{22} & 23 & \colorbox{red}{24} & 25 & \colorbox{red}{26} & 27 \\ \colorbox{red}{28} & 29 & \colorbox{red}{30} & 31 & \colorbox{red}{32} & 33 & \colorbox{red}{34} \\ 35 & \colorbox{red}{36} & 37 & \colorbox{red}{38} & 39 & \colorbox{red}{40} & 41 \\ \colorbox{red}{42} & 43 & \colorbox{red}{44} & 45 & \colorbox{red}{46} & 47 & \colorbox{red}{48} \\ \end{matrix} $$

Next, we move to the following unmarked number, 3, and mark all its multiples (say with green) $$ \begin{matrix} 0 & 1 & 2 & 3 & \colorbox{red}{4} & 5 & \colorbox{red}{6} \\ 7 & \colorbox{red}{8} & \colorbox{green}{9} & \colorbox{red}{10} & 11 & \colorbox{red}{12} & 13 \\ \colorbox{red}{14} & \colorbox{green}{15} & \colorbox{red}{16} & 17 & \colorbox{red}{18} & 19 & \colorbox{red}{20} \\ \colorbox{green}{21} & \colorbox{red}{22} & 23 & \colorbox{red}{24} & 25 & \colorbox{red}{26} & \colorbox{green}{27} \\ \colorbox{red}{28} & 29 & \colorbox{red}{30} & 31 & \colorbox{red}{32} & \colorbox{green}{33} & \colorbox{red}{34} \\ 35 & \colorbox{red}{36} & 37 & \colorbox{red}{38} & \colorbox{green}{39} & \colorbox{red}{40} & 41 \\ \colorbox{red}{42} & 43 & \colorbox{red}{44} & \colorbox{green}{45} & \colorbox{red}{46} & 47 & \colorbox{red}{48} \\ \end{matrix} $$

Next, we proceed to the unmarked number 5 and mark all its multiples (say blue).

$$ \begin{matrix} 0 & 1 & 2 & 3 & \colorbox{red}{4} & 5 & \colorbox{red}{6} \\ 7 & \colorbox{red}{8} & \colorbox{green}{9} & \colorbox{red}{10} & 11 & \colorbox{red}{12} & 13 \\ \colorbox{red}{14} & \colorbox{green}{15} & \colorbox{red}{16} & 17 & \colorbox{red}{18} & 19 & \colorbox{red}{20} \\ \colorbox{green}{21} & \colorbox{red}{22} & 23 & \colorbox{red}{24} & \colorbox{blue}{25} & \colorbox{red}{26} & \colorbox{green}{27} \\ \colorbox{red}{28} & 29 & \colorbox{red}{30} & 31 & \colorbox{red}{32} & \colorbox{green}{33} & \colorbox{red}{34} \\ \colorbox{blue}{35} & \colorbox{red}{36} & 37 & \colorbox{red}{38} & \colorbox{green}{39} & \colorbox{red}{40} & 41 \\ \colorbox{red}{42} & 43 & \colorbox{red}{44} & \colorbox{green}{45} & \colorbox{red}{46} & 47 & \colorbox{red}{48} \\ \end{matrix} $$

We repeat this process, resulting in the final table shown below:

Therefore, the prime numbers are those that remain unmarked: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47.

Code

Java

import java.util.ArrayList;
import java.util.List;

public class SieveOfEratosthenes {
    public static List<Integer> sieveOfEratosthenes(int n) {
        boolean[] isPrime =
            new boolean[n + 1]; // Create a boolean array of n+1 size
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true; // Initialize all entries as true. A value will
                               // be false if it is NOT a prime.
        }

        for (int p = 2; p * p <= n; p++) {
            // If isPrime[p] is not changed, then it is a prime
            if (isPrime[p]) {
                // Update all multiples of p to false
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // Collect all prime numbers
        List<Integer> primeNumbers = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primeNumbers.add(i);
            }
        }

        return primeNumbers;
    }
}

Complexity

⏰ Time complexity: O(n ln ln n)
- The outer loop runs from 2 to √n.
- For each prime number p, you mark its multiples. The number of operations for each prime p is n/p.
- The total number of operations is approximately: $n \left( \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \cdots \right)$
- The series inside the parentheses is the Harmonic series of the primes, which is known to converge to $\ln(\ln(n))$.
- 1. - Therefore, the overall complexity is $O(n \cdot \ln(\ln(n)))$.
🧺 Space complexity: O(n) for using isPrime array

Problem#

Examples#

Solution#

Algorithm#

Dry Run#

Code#

Java#

Complexity#