Sieve of Eratosthenes
Find all primes up to N by eliminating multiples.
How it works
The Sieve of Eratosthenes, described by the Greek mathematician Eratosthenes around 240 BC, is one of the oldest known algorithms still used in production software today. It operates on a boolean array of size n+1 and works by an elegantly simple insight: starting from the smallest prime (2), mark all of its multiples as composite; advance to the next unmarked number (which must be prime) and repeat. Crucially, multiples of p need only start from p², because any smaller multiple p×k (k < p) was already eliminated when we processed k.
The outer loop needs only run while p² ≤ n, giving the algorithm its O(n log log n) time complexity — a consequence of the harmonic series summed over prime reciprocals. The space requirement is O(n) for the boolean array, which in practice can be compressed to a bitset (1 bit per number) so that a sieve up to 10⁸ fits in just 12 MB of RAM. Further optimizations like the segmented sieve allow computing primes in ranges far beyond available memory by processing the number line in cache-sized chunks.
The sieve's combination of extreme simplicity, provable correctness, and near-linear performance has kept it relevant for over two millennia. Modern applications include precomputing prime tables for competitive programming, generating large primes for cryptographic key material, and factorization by trial division using the precomputed prime list.
Complexity
Visualizer
Where it's used in the real world
Cryptographic libraries (OpenSSL, BoringSSL)
Candidate prime sieving during RSA key generationRSA requires two large prime numbers. Generating them involves sieving candidate integers against small primes (up to ~2000) to quickly reject composites before running the expensive Miller-Rabin primality test. Sieving eliminates ~70% of candidates with negligible CPU cost.
Competitive programming judges (Codeforces, LeetCode)
Precomputed prime tables for number-theory problemsProblems involving prime factorization, Euler's totient, or Möbius function are solved in O(1) per query after a one-time O(n log log n) sieve. Contestants run the sieve at program startup to build a primes list and smallest-prime-factor table reused across all test cases.
Embedded systems / firmware
Prime tables for CRC polynomial selectionCRC error-detection codes require primitive polynomials over GF(2), whose degrees are tied to prime exponents. Embedded toolchains use a sieve to generate the relevant prime table at compile time, storing only the bitset in read-only flash memory to minimize footprint.
Implementation
function sieveOfEratosthenes(limit: number): number[] {
const isPrime = new Uint8Array(limit + 1).fill(1);
isPrime[0] = 0;
if (limit >= 1) isPrime[1] = 0;
for (let p = 2; p * p <= limit; p++) {
if (isPrime[p]) {
for (let m = p * p; m <= limit; m += p) {
isPrime[m] = 0;
}
}
}
const primes: number[] = [];
for (let i = 2; i <= limit; i++) {
if (isPrime[i]) primes.push(i);
}
return primes;
}
// Usage
console.log(sieveOfEratosthenes(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]