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](prime-numbers-up-to-n) and here we will cover Sieve of Eratosthenes Algorithm.

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:

1. 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.
2. 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.

Now, As per the algorithm, we will mark all numbers that are divisible by 2 (say with red)

Next, we move to the following unmarked number, 3, and mark all its multiples (say with green)

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

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++

#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

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

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

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

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