Sieve of Eratosthenes

Given a number n, your task is to find all prime numbers less than or equal to n using the Sieve of Eratosthenes algorithm.

This classic algorithm eliminates the multiples of each prime number starting from 2, leading to an efficient list of primes up to n.

Understanding the Problem

We are given a number n, and our goal is to find all prime numbers less than or equal to n. A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Instead of checking each number individually, we will use an efficient algorithm called the Sieve of Eratosthenes. This method uses the principle of marking the multiples of each prime starting from 2, so that only primes remain unmarked.

Step-by-Step Solution with Example

Let’s understand the Sieve of Eratosthenes with an example where n = 30.

Step 1: Create a list of size n+1 and assume all numbers from 2 to n are prime

We initialize a boolean array isPrime[] of size n + 1 with all entries set to true, except for index 0 and 1 which we mark as false because 0 and 1 are not prime numbers.

Step 2: Start from the first prime number, p = 2

We begin our iteration with the smallest prime number, which is 2.

Step 3: Mark all multiples of p (starting from p*p) as not prime

We mark all numbers like 4, 6, 8... up to 30 as false because they are multiples of 2.

Step 4: Move to the next number p = 3

Since isPrime[3] is still true, we know it’s prime. Now mark all multiples of 3 such as 9, 12, 15... up to 30 as false.

Step 5: Continue this process for the next numbers

We repeat this for the next numbers (4 is skipped since it’s already marked false). For p = 5, we mark 25 and 30 as false. We stop this loop when p * p > n (i.e., when p becomes greater than √n).

Step 6: Collect all numbers that are still marked true

Finally, we collect all indices in isPrime[] that are still true. These are our prime numbers up to n.

Final List for n = 30

The prime numbers ≤ 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Edge Cases

• n = 0 or n = 1: There are no prime numbers. We return an empty list.
• n = 2: The only prime number is 2.
• Negative n: Prime numbers are not defined for negative integers. We return an empty list or raise an error depending on design.

Final Thoughts

The Sieve of Eratosthenes is one of the most efficient ways to find all primes up to a given number. It avoids redundant checks by eliminating multiples early. It is especially useful when n is large, and you need all primes up to that number quickly. Beginners should focus on understanding how marking from p*p helps reduce unnecessary operations.

1. Create a boolean array isPrime[] of size n+1 and initialize all entries as true. A value in isPrime[i] will finally be false if i is not a prime, else true.
2. Start from the first prime number, p = 2.
3. For each p, if isPrime[p] is true, mark all multiples of p as false (i.e., isPrime[i] = false for i = p*p to n, incrementing by p).
4. Repeat the process for the next number until p*p <= n.
5. All numbers i for which isPrime[i] is true are the prime numbers up to n.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieveOfEratosthenes(int n) {
    bool isPrime[n+1];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;

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

    printf("Prime numbers up to %d: ", n);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieveOfEratosthenes(n);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n+1, true);
    isPrime[0] = false;
    isPrime[1] = false;

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

    cout << "Prime numbers up to " << n << ": ";
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) cout << i << " ";
    }
    cout << endl;
}

int main() {
    int n = 50;
    sieveOfEratosthenes(n);
    return 0;
}

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False

    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p*p, n+1, p):
                is_prime[i] = False
        p += 1

    primes = [i for i in range(2, n+1) if is_prime[i]]
    print(f"Prime numbers up to {n}:", primes)

if __name__ == "__main__":
    n = 50
    sieve_of_eratosthenes(n)

public class SieveOfEratosthenes {
    public static void sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n+1];
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = false;
        isPrime[1] = false;

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

        System.out.print("Prime numbers up to " + n + ": ");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 50;
        sieveOfEratosthenes(n);
    }
}

function sieveOfEratosthenes(n) {
  const isPrime = new Array(n+1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;

  for (let p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
      for (let i = p * p; i <= n; i += p) {
        isPrime[i] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  console.log(`Prime numbers up to ${n}:`, primes);
}

const n = 50;
sieveOfEratosthenes(n);

package main

import "fmt"

func sieveOfEratosthenes(n int) {
    isPrime := make([]bool, n+1)
    for i := 0; i <= n; i++ {
        isPrime[i] = true
    }
    isPrime[0] = false
    isPrime[1] = false

    for p := 2; p*p <= n; p++ {
        if isPrime[p] {
            for i := p * p; i <= n; i += p {
                isPrime[i] = false
            }
        }
    }

    fmt.Printf("Prime numbers up to %d: ", n)
    for i := 2; i <= n; i++ {
        if isPrime[i] {
            fmt.Printf("%d ", i)
        }
    }
    fmt.Println()
}

func main() {
    n := 50
    sieveOfEratosthenes(n)
}

fn sieve_of_eratosthenes(n: usize) {
    let mut is_prime = vec![true; n+1];
    is_prime[0] = false;
    is_prime[1] = false;

    let limit = (n as f64).sqrt() as usize;
    for p in 2..=limit {
        if is_prime[p] {
            let mut i = p * p;
            while i <= n {
                is_prime[i] = false;
                i += p;
            }
        }
    }

    print!("Prime numbers up to {}: ", n);
    for i in 2..=n {
        if is_prime[i] {
            print!("{} ", i);
        }
    }
    println!();
}

fn main() {
    let n = 50;
    sieve_of_eratosthenes(n);
}

fun sieveOfEratosthenes(n: Int) {
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    var p = 2
    while (p * p <= n) {
        if (isPrime[p]) {
            var i = p * p
            while (i <= n) {
                isPrime[i] = false
                i += p
            }
        }
        p++
    }

    print("Prime numbers up to $n: ")
    for (i in 2..n) {
        if (isPrime[i]) print("$i ")
    }
    println()
}

fun main() {
    val n = 50
    sieveOfEratosthenes(n)
}

func sieveOfEratosthenes(_ n: Int) {
    var isPrime = Array(repeating: true, count: n + 1)
    isPrime[0] = false
    isPrime[1] = false

    var p = 2
    while p * p <= n {
        if isPrime[p] {
            var i = p * p
            while i <= n {
                isPrime[i] = false
                i += p
            }
        }
        p += 1
    }

    print("Prime numbers up to \(n):", terminator: " ")
    for i in 2...n {
        if isPrime[i] {
            print(i, terminator: " ")
        }
    }
    print()
}

let n = 50
sieveOfEratosthenes(n)

function sieveOfEratosthenes(n: number): void {
  const isPrime: boolean[] = new Array(n + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;

  for (let p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
      for (let i = p * p; i <= n; i += p) {
        isPrime[i] = false;
      }
    }
  }

  const primes: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  console.log(`Prime numbers up to ${n}:`, primes);
}

const n: number = 50;
sieveOfEratosthenes(n);

Time complexity

Space complexity

O(n)

A boolean array of size n+1 is used to keep track of prime statuses for all numbers from 0 to n, which requires O(n) space.