Sieve of Eratosthenes: Prime Number Generation

Key Insights

The Sieve of Eratosthenes achieves O(n log log n) time complexity, making it dramatically faster than trial division for generating all primes up to n, but its O(n) space requirement becomes the limiting factor for very large ranges.
Simple optimizations like skipping even numbers and starting elimination at p² can cut runtime in half with minimal code changes—always implement these in production code.
For ranges beyond a few billion, switch to a segmented sieve or probabilistic primality tests; knowing when to abandon the classic sieve is as important as implementing it correctly.

Why Prime Numbers Matter

Prime numbers sit at the foundation of modern computing. RSA encryption relies on the difficulty of factoring large semiprimes. Hash table implementations use prime bucket counts to reduce collision clustering. Pseudorandom number generators incorporate prime moduli for better distribution properties.

When you need primes, you typically need many of them, and you need them fast. Trial division—checking each candidate against all smaller primes—works for small ranges but collapses under scale. Testing whether a single number n is prime takes O(√n) operations. Generating all primes up to n using trial division costs O(n√n), which becomes painful around n = 10⁷.

The Sieve of Eratosthenes, devised over 2,200 years ago by a Greek mathematician, remains one of the most elegant solutions to this problem. It flips the approach: instead of testing each number for primality, it systematically eliminates composite numbers, leaving only primes behind.

The Algorithm Explained

The sieve works through elimination. Start with a list of all integers from 2 to n. Take the first unmarked number (2), mark it as prime, then cross out all its multiples. Move to the next unmarked number (3), mark it as prime, cross out its multiples. Repeat until you’ve processed all numbers up to √n.

Here’s the process for n = 30:

Start: 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
Cross out multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
Cross out multiples of 3: 9, 15, 21, 27 (6, 12, 18, 24, 30 already crossed)
Cross out multiples of 5: 25 (10, 15, 20, 30 already crossed)
√30 ≈ 5.5, so we stop here

Remaining unmarked: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29—all primes up to 30.

def sieve_basic(n):
    """Basic Sieve of Eratosthenes implementation."""
    if n < 2:
        return []
    
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    return [i for i in range(2, n + 1) if is_prime[i]]

Notice the inner loop starts at i * i rather than 2 * i. Any composite number smaller than i² with factor i has already been marked when processing a smaller prime factor. This optimization comes free and roughly halves the work.

Time and Space Complexity Analysis

The sieve’s time complexity is O(n log log n). This comes from summing the work done for each prime p: we mark n/p composites. The sum of n/p for all primes p ≤ n equals n × Σ(1/p), and the sum of reciprocals of primes up to n grows as log log n (Mertens’ theorem).

Space complexity is O(n) for the boolean array. Each boolean typically consumes 1 byte in most implementations, so sieving to 10⁹ requires roughly 1 GB of memory.

Compare this to trial division:

Method	Time Complexity	Space Complexity
Trial Division	O(n√n)	O(π(n)) ≈ O(n/ln n)
Basic Sieve	O(n log log n)	O(n)

For n = 10⁸, trial division performs roughly 10¹² operations. The sieve performs about 4 × 10⁸. That’s a 2,500x speedup.

Optimizations and Variants

The basic implementation leaves performance on the table. Here’s an optimized version that handles only odd numbers and uses wheel factorization for 2 and 3:

def sieve_optimized(n):
    """Optimized sieve skipping even numbers."""
    if n < 2:
        return []
    if n == 2:
        return [2]
    
    # Only track odd numbers: index i represents number 2i + 1
    size = (n - 1) // 2
    is_prime = [True] * (size + 1)
    
    for i in range(1, int(n ** 0.5) // 2 + 1):
        if is_prime[i]:
            # i represents prime p = 2i + 1
            # Start crossing at p², which maps to index (p² - 1) / 2
            p = 2 * i + 1
            start = (p * p - 1) // 2
            for j in range(start, size + 1, p):
                is_prime[j] = False
    
    primes = [2]
    primes.extend(2 * i + 1 for i in range(1, size + 1) if is_prime[i])
    return primes

This cuts memory usage in half and eliminates half the iterations. For even better memory efficiency with large ranges, use a segmented sieve:

def segmented_sieve(n, segment_size=32768):
    """Memory-efficient segmented sieve."""
    if n < 2:
        return []
    
    limit = int(n ** 0.5) + 1
    small_primes = sieve_optimized(limit)
    
    primes = list(small_primes)
    
    for low in range(limit, n + 1, segment_size):
        high = min(low + segment_size - 1, n)
        segment = [True] * (high - low + 1)
        
        for p in small_primes:
            # Find first multiple of p >= low
            start = ((low + p - 1) // p) * p
            if start == p:
                start = p * p
            
            for j in range(start, high + 1, p):
                segment[j - low] = False
        
        primes.extend(i for i in range(low, high + 1) if segment[i - low])
    
    return primes

The segmented sieve uses O(√n + segment_size) memory regardless of n. You can sieve to 10¹² with a few megabytes of RAM.

Practical Applications

Once you have a prime sieve, prime factorization becomes trivial. Precompute the smallest prime factor for each number, then factor any number in O(log n) time:

def build_spf(n):
    """Build smallest prime factor array."""
    spf = list(range(n + 1))  # spf[i] = i initially
    
    for i in range(2, int(n ** 0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i * i, n + 1, i):
                if spf[j] == j:
                    spf[j] = i
    
    return spf

def factorize(n, spf):
    """Factorize n using precomputed SPF array."""
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors

# Usage
spf = build_spf(1000000)
print(factorize(84, spf))  # [2, 2, 3, 7]
print(factorize(997, spf))  # [997] - prime

This pattern appears constantly in competitive programming. Problems involving divisor counts, GCDs across ranges, or multiplicative functions often reduce to fast factorization.

Language-Specific Implementations

Python’s interpreter overhead makes it poorly suited for tight loops. NumPy’s vectorized operations help significantly:

import numpy as np

def sieve_numpy(n):
    """NumPy-vectorized sieve implementation."""
    is_prime = np.ones(n + 1, dtype=bool)
    is_prime[:2] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = False
    
    return np.nonzero(is_prime)[0]

For maximum performance, use bitwise operations in C:

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

#define GET_BIT(arr, i) ((arr[(i) >> 3] >> ((i) & 7)) & 1)
#define CLEAR_BIT(arr, i) (arr[(i) >> 3] &= ~(1 << ((i) & 7)))

void sieve_bitwise(int n, unsigned char *primes) {
    memset(primes, 0xFF, (n >> 3) + 1);
    CLEAR_BIT(primes, 0);
    CLEAR_BIT(primes, 1);
    
    for (int i = 2; i * i <= n; i++) {
        if (GET_BIT(primes, i)) {
            for (int j = i * i; j <= n; j += i) {
                CLEAR_BIT(primes, j);
            }
        }
    }
}

The bitwise version uses 8x less memory than a boolean array and benefits from cache efficiency. Benchmarking on my machine for n = 10⁸: pure Python takes 25 seconds, NumPy takes 1.2 seconds, and optimized C takes 0.4 seconds.

Limitations and Alternatives

The sieve hits practical limits around n = 10¹⁰ to 10¹¹. Beyond that, even segmented sieves become slow, and you’re better off with probabilistic primality tests.

Miller-Rabin determines whether a single number is probably prime in O(k log³ n) time, where k is the number of rounds. For cryptographic applications where you need a few large primes rather than all primes in a range, Miller-Rabin wins decisively.

Use the sieve when:

You need all primes up to n (n ≤ 10⁹ or so)
You need to answer many “is x prime?” queries for x ≤ n
You need fast factorization for many numbers ≤ n

Use probabilistic tests when:

You need to test individual large numbers (n > 10¹²)
You’re generating cryptographic primes
Memory is constrained and n is large

The Sieve of Eratosthenes has survived 2,200 years because it works. Understand it, optimize it appropriately for your use case, and know when to reach for something else.