Sieve of Eratosthenes: Find All Primes Efficiently

Sieve of Eratosthenes

Mark composite numbers by iterating multiples of each prime from 2 to sqrt(n).

Algorithm

Create boolean array is_prime[0..n], all True
Set is_prime[0] = is_prime[1] = False
For p = 2 to sqrt(n):
    if is_prime[p]:
        for multiple = p*p to n step p:
            is_prime[multiple] = False
Primes = {i : is_prime[i] is True}

Why start at p*p? Smaller multiples (2p, 3p, ...) already marked by smaller primes.

C Implementation

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

void sieve(int n, bool *is_prime) {
    for (int i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int m = p * p; m <= n; m += p)
                is_prime[m] = false;
        }
    }
}

int main() {
    int n = 50;
    bool is_prime[51];
    sieve(n, is_prime);
    printf("Primes up to %d: ", n);
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) printf("%d ", i);
    printf("\n");
    return 0;
}

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

vector<int> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; (long long)p * p <= n; p++) {
        if (is_prime[p]) {
            for (int m = p * p; m <= n; m += p)
                is_prime[m] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    auto primes = sieve(50);
    for (int p : primes) cout << p << " ";
    cout << endl;
    return 0;
}

Java Implementation

import java.util.*;

public class Sieve {
    public static List<Integer> sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; (long) p * p <= n; p++) {
            if (isPrime[p]) {
                for (int m = p * p; m <= n; m += p)
                    isPrime[m] = false;
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++)
            if (isPrime[i]) primes.add(i);
        return primes;
    }

    public static void main(String[] args) {
        System.out.println(sieve(50));
    }
}

JavaScript Implementation

function sieve(n) {
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (let m = p * p; m <= n; m += p)
                isPrime[m] = false;
        }
    }
    return Array.from({length: n - 1}, (_, i) => i + 2).filter(i => isPrime[i]);
}

console.log(sieve(50));

Python Implementation

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
        p += 1
    return [i for i in range(2, n + 1) if is_prime[i]]

print(sieve(50))  # [2, 3, 5, 7, 11, 13, ...]

Smallest Prime Factor (SPF) Sieve

Enables O(log n) factorization after O(n log log n) build:

def spf_sieve(n):
    spf = list(range(n + 1))
    for p in range(2, int(n**0.5) + 1):
        if spf[p] == p:  # p is prime
            for m in range(p * p, n + 1, p):
                if spf[m] == m:
                    spf[m] = p
    return spf

def factorize(n, spf):
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors

Complexity

Time: O(n log log n)
Space: O(n)