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. We have this problem here - Prime numbers up to n and here we will cover Sieve of Eratosthenes Algorithm.

Examples

Example 1:

1
2


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

Example 2:

1
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

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <vector>
using namespace std;

class Solution {
 public:
    vector<int> primesUpto(int n) {
        if (n < 2) return {};
        vector<char> isPrime(n + 1, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; 1LL * p * p <= n; ++p) {
            if (!isPrime[p]) continue;
            for (int j = p * p; j <= n; j += p) isPrime[j] = false;
        }
        vector<int> ans;
        for (int i = 2; i <= n; ++i) if (isPrime[i]) ans.push_back(i);
        return ans;
    }
};

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


package main

type Solution struct{}

func (s *Solution) PrimesUpto(n int) []int {
    if n < 2 { return []int{} }
    isPrime := make([]bool, n+1)
    for i := range isPrime { isPrime[i] = true }
    isPrime[0], isPrime[1] = false, false
    for p := 2; p*p <= n; p++ {
        if !isPrime[p] { continue }
        for j := p*p; j <= n; j += p { isPrime[j] = false }
    }
    ans := make([]int, 0)
    for i := 2; i <= n; i++ { if isPrime[i] { ans = append(ans, i) } }
    return ans
}

Java

 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


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

class Solution {
    public List<Integer> primesUpto(int n) {
        List<Integer> primeNumbers = new ArrayList<>();
        if (n < 2) return primeNumbers;

        // Create a boolean array of n+1 size. A value in isPrime[i] will be false
        // if i is not a prime, otherwise true.
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true; // Initialize all entries as true.
        }

        // Mark non-primes using Sieve of Eratosthenes
        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
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primeNumbers.add(i);
            }
        }

        return primeNumbers;
    }
}

Kotlin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    fun primesUpto(n: Int): List<Int> {
        if (n < 2) return emptyList()
        val isPrime = BooleanArray(n + 1) { true }
        isPrime[0] = false; isPrime[1] = false
        var p = 2
        while (p * p <= n) {
            if (isPrime[p]) {
                var j = p * p
                while (j <= n) {
                    isPrime[j] = false
                    j += p
                }
            }
            p++
        }
        val ans = mutableListOf<Int>()
        for (i in 2..n) if (isPrime[i]) ans.add(i)
        return ans
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
        def primesUpto(self, n: int) -> list[int]:
                if n < 2:
                        return []
                is_prime = [True] * (n + 1)
                is_prime[0] = is_prime[1] = False
                p = 2
                while p * p <= n:
                        if is_prime[p]:
                                for j in range(p * p, n + 1, p):
                                        is_prime[j] = False
                        p += 1
                return [i for i in range(2, n + 1) if is_prime[i]]

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))$.
- 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#

C++#

Go#

Java#

Kotlin#

Python#

Complexity#