vault

Sieve of Eratosthenes

24 min read

Sieve of Eratosthenes

The Sieve of Eratosthenes finds every prime number up to a bound n in O(n log log n) time and O(n) space, using only addition and array writes — no division, no modulo, no primality testing. The algorithm, attributed to Eratosthenes of Cyrene (~276–194 BCE, librarian of Alexandria) and described in Nicomachus of Gerasa’s Introduction to Arithmetic (~100 CE), is the oldest non-trivial number-theoretic algorithm still in active production use. It works by eliminating composites rather than certifying primes: maintain a boolean array indicating “this index might be prime,” then for each unmarked prime p in turn, mark every multiple of p (starting from p²) as composite. Whatever survives the sieve is prime. This note derives the algorithm, proves its complexity (the log log n factor comes from Mertens’ theorem on the sum of reciprocals of primes), discusses the standard optimizations (skip even numbers, segmented sieve for memory-bounded large inputs, wheel factorization), and contrasts it with the linear sieve and the asymptotically faster but practically slower Sieve of Atkin.

1. Intuition — Sifting Stones

The Greek verb koskineuein means “to sift through a sieve.” Eratosthenes’ analogy was concrete: imagine a list of pebbles labeled with the integers from 2 up to n. You hold a sieve with holes spaced exactly 2 apart and shake out every pebble at index 4, 6, 8, … — these are the multiples of 2 (excluding 2 itself, which sits on top of the sieve). Then you take the next pebble that did not fall through — pebble 3 — and use a sieve with holes spaced 3 apart, shaking out 6, 9, 12, … . Then 5, then 7, and so on. The pebbles that never fell through are the primes.

Translated into algorithmic terms: maintain a boolean array is_prime[2..n], initially all True. For each i in increasing order, if is_prime[i] is still True, then i is prime — and we can mark every multiple of i (2i, 3i, 4i, …) as composite. The crucial correctness argument is that every composite has a smallest prime factor, and we will encounter that factor before the composite, mark the composite as such, and never report it as prime.

Why start marking from p² rather than from 2p? Any composite k · p with k < p was already marked by some prime smaller than p, because k has a prime factor q ≤ k < p, and k · p is a multiple of q already crossed out. So the smallest new multiple of p to mark is p · p = p². This optimization halves the work in practice and is essential for the asymptotic bound.

This is fundamentally different from a primality test (e.g., trial division, Miller-Rabin Primality Test). The sieve produces all primes up to n together; a primality test certifies a single number. The sieve is faster per-prime when you need many primes; trial division wins when you need only one or two. Eratosthenes is the canonical batch algorithm for primes.

2. Tiny Worked Example — Sieve up to n = 30

Initial state — boolean array indexed 0 through 30, all True except indices 0 and 1 (not prime by definition):

idx:   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
state: T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T  T

Step 1: p = 2 is True, so 2 is prime. Mark multiples of 2 starting from 2² = 4:

idx:   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
state: T  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

Step 2: p = 3 is True, so 3 is prime. Mark multiples of 3 starting from 3² = 9:

idx:   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
state: T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F

(Indices 9, 15, 21, 27 were freshly marked; 12, 18, 24, 30 were already marked by step 1.)

Step 3: p = 5 is True, so 5 is prime. Mark multiples of 5 starting from 5² = 25:

idx:   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
state: T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  F  F  F  F  T  F

(Index 25 freshly marked.)

Step 4: p = 7. But p² = 49 > 30, so we can stop. Every composite ≤ 30 has been struck out by a prime ≤ √30 ≈ 5.48, and we just processed primes 2, 3, 5.

Reading off the True entries: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — the 10 primes up to 30. By the prime-counting function π(30) = 10, this is correct.

The early-stopping rule p² > n is not optional for performance — it is the reason the inner loop is bounded by √n distinct outer iterations. Without it, you would waste time launching mark loops for primes whose square already exceeds n.

3. The Algorithm

3.1 Pseudocode

sieve_eratosthenes(n):
    is_prime := array of length n+1, initialized to True
    is_prime[0] := False
    is_prime[1] := False
    p := 2
    while p * p <= n:
        if is_prime[p]:
            for k := p*p, p*p + p, p*p + 2*p, ..., k <= n:
                is_prime[k] := False
        p := p + 1
    primes := [i for i in 0..n if is_prime[i]]
    return primes

Three points to internalize:

  1. The outer loop bound is p * p ≤ n, equivalently p ≤ √n. Beyond this, no further marks happen because the smallest unmarked multiple p² is already out of range.
  2. The inner loop start is p², not 2p. Anything below p² was already marked by a smaller prime.
  3. The inner loop step is p. We jump by p to land on every multiple of p exactly once. This is what makes the inner loop’s cost n / p per prime p, summing to the famous O(n log log n).

3.2 Python Implementation

def sieve_eratosthenes(n: int) -> list[int]:
    """Return all primes p with 2 <= p <= n, using O(n) space, O(n log log n) time."""
    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]:
            # Slice assignment is the canonical Python idiom — internally a tight C loop.
            is_prime[p*p : n+1 : p] = [False] * len(range(p*p, n+1, p))
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]
 
# Optimization: separate the even number case, then iterate only odd p
def sieve_eratosthenes_odd_only(n: int) -> list[int]:
    """Same algorithm, ~2x speedup by handling 2 separately and iterating odd p only."""
    if n < 2:
        return []
    if n == 2:
        return [2]
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    # Mark every even number > 2 as composite up front
    for k in range(4, n + 1, 2):
        is_prime[k] = False
    # Now only test odd p, and for each prime p, mark only odd multiples
    p = 3
    while p * p <= n:
        if is_prime[p]:
            # Step by 2*p so we hit only odd multiples (even ones already marked)
            is_prime[p*p : n+1 : 2*p] = [False] * len(range(p*p, n+1, 2*p))
        p += 2
    return [i for i, prime in enumerate(is_prime) if prime]
 
# Compact bit-vector version: 8x memory savings using 1 bit per entry
import array
def sieve_bitvector(n: int) -> list[int]:
    if n < 2:
        return []
    # Use Python's bytearray as a packed boolean array
    bv = bytearray(b"\x01") * (n + 1)
    bv[0] = bv[1] = 0
    p = 2
    while p * p <= n:
        if bv[p]:
            for k in range(p * p, n + 1, p):
                bv[k] = 0
        p += 1
    return [i for i in range(n + 1) if bv[i]]

The slice-assignment idiom is_prime[p*p : n+1 : p] = [False] * count exploits CPython’s C-level slice machinery — far faster than a Python for loop with is_prime[k] = False. For n = 10^7 this difference is ~10× in wall time on CPython.

For maximum-performance Python, use numpy boolean arrays or the array module’s typed arrays; even better, drop to C via Cython or call out to a vectorized library. The pure-Python sieve with slice assignment is fast enough for n up to ~10^7 in interview settings.

4. Complexity — Deriving O(n log log n)

4.1 The Total Number of Inner-Loop Iterations

For each prime p ≤ √n, the inner loop marks ⌊n / p⌋ − p + 1 ≈ n/p multiples (it actually starts at p² not p, so the count is ⌊(n − p²) / p⌋ + 1 ≈ n/p − p). Summing over all primes p ≤ √n:

T(n)  =  Σ_{p prime, p ≤ √n} (n/p − p + O(1))
     ≤  n · Σ_{p prime, p ≤ √n} (1/p)

The total work is dominated by the sum of reciprocals of primes up to √n.

It is worth being precise about which sum appears, because textbooks differ. The cp-algorithms derivation analyzes the un-optimized sieve that launches a mark loop for every prime (not just those ≤ √n), giving total work Σ_{p ≤ n} n/p = n · Σ_{p ≤ n} 1/p (cp-algorithms). That sum is Θ(log log n) by Mertens’ theorem (§4.2), so the bound is O(n log log n). Restricting the outer loop to p ≤ √n (the early-stop optimization of §2) only shrinks the sum — to Σ_{p ≤ √n} 1/p, which is also Θ(log log n) (shown below) — so it improves the constant but not the asymptotic class. Either way the answer is O(n log log n); we derive it via the √n form because that is what the optimized code actually executes.

4.2 Mertens’ Theorem on Prime Reciprocals

Franz Mertens proved in 1874:

Σ_{p prime, p ≤ N} (1/p)  =  log log N  +  M  +  o(1)

where M ≈ 0.2614972… is the Meissel-Mertens constant. The asymptotic growth is log log N. (See Mertens’ theorems on Wikipedia for the formal statement and proof. Hardy & Wright Theorem 427 gives a proof.)

So substituting N = √n:

Σ_{p prime, p ≤ √n} (1/p)  =  log log √n  +  O(1)
                            =  log (½ log n)  +  O(1)
                            =  log log n  −  log 2  +  O(1)
                            =  Θ(log log n)

(The log 2 is absorbed into the O(1).) Therefore:

T(n)  ≤  n · Θ(log log n)  =  O(n log log n)

That is the famous bound. The log log n factor is so small it is essentially constant for any practical input: for n = 10^9, log log n ≈ 3 (using natural log). The sieve is, for all practical purposes, linear time.

4.3 Space — O(n) and Why It Matters

The boolean array uses n bits at minimum, or n bytes if implemented with a naive bool[] (Python’s [True] * n uses ~28 bytes per entry due to object overhead, so naive Python sieves are very memory-hungry). For n = 10^9, even with a tight bitset (n/8 bytes ≈ 125 MB), the sieve fits in RAM. For n = 10^11, it does not — and the segmented sieve (§5) becomes necessary.

The space is what differentiates Eratosthenes from primality-testing approaches: a Miller-Rabin sweep over the integers up to n uses O(1) working memory but takes much longer per integer. For “give me all primes up to a billion,” Eratosthenes wins; for “is this 1024-bit number prime?”, Miller-Rabin wins. Different tools for different jobs.

5. Optimizations

5.1 Skip Even Numbers (2× Speedup)

Half the numbers ≤ n are even, and only 2 is prime among them. Handling 2 specially (mark all even composites in one shot) and then iterating only odd p, with inner loops stepping by 2p (to skip the even multiples already marked), halves the work. The sieve_eratosthenes_odd_only Python function in §3.2 implements this.

5.2 Wheel Factorization

Generalize the “skip even numbers” trick: a k-wheel skips multiples of the first k primes (the wheel primes). For example, the 2-3 wheel skips multiples of 2 and 3 — only 1/3 of integers (those ≡ 1, 5 (mod 6)) are sieved. The 2-3-5 wheel skips multiples of 2, 3, 5 — only 8/30 ≈ 27% of integers are sieved. Higher wheels save more but require larger lookup tables and more complex indexing.

Wheel factorization is the standard high-performance optimization in production sieves (e.g., Kim Walisch’s primesieve, which sieves up to 10^15 in seconds, uses a 2-3-5-7 wheel).

5.3 Segmented Sieve

For n too large to fit a single boolean array in memory, sieve in segments of size √n (or some cache-friendly size like 32 KB):

  1. Find all primes up to √n with a basic sieve.
  2. For each segment [L, R] with R − L ≈ √n (or a chosen segment size), allocate a small boolean array. For each prime p ≤ √n, find the smallest multiple of p that is ≥ L and mark every p-th index up to R.
  3. Read off the segment’s primes and move on.

Total time: still O(n log log n). Total memory: O(√n + S) — the O(√n) table of small primes (precisely π(√n) ≈ √n / ln √n entries) plus the segment buffer of size S (cp-algorithms). The segmented sieve is what makes n = 10^12 feasible on commodity hardware, and it is the design used by production sieves such as primesieve (§5.5).

def segmented_sieve(n: int, segment_size: int = 32_768) -> list[int]:
    """Memory-efficient sieve for large n. O(sqrt(n)) memory in the small-primes table."""
    import math
    sqrt_n = int(math.isqrt(n))
    small_primes = sieve_eratosthenes(sqrt_n)
    primes = list(small_primes)
    low = sqrt_n + 1
    while low <= n:
        high = min(low + segment_size - 1, n)
        is_prime_seg = [True] * (high - low + 1)
        for p in small_primes:
            # First multiple of p in [low, high]: ceil(low / p) * p
            start = max(p * p, ((low + p - 1) // p) * p)
            for k in range(start, high + 1, p):
                is_prime_seg[k - low] = False
        for i, flag in enumerate(is_prime_seg):
            if flag:
                primes.append(low + i)
        low = high + 1
    return primes

The segment size is typically chosen to fit the L2 or L3 cache of the target CPU; in the inner loop, the boolean array is touched repeatedly, and cache hits dominate performance.

5.4 Linear Sieve (O(n) Time)

The classical Eratosthenes sieve marks each composite multiple times — 12 is marked by 2 and by 3, 30 is marked by 2, 3, and 5. The linear sieve (also called the Euler sieve; sometimes attributed to Mairson 1977) marks each composite exactly once, achieving O(n) time at the cost of more bookkeeping. The trick: when sieving with prime p, only mark composites k · p where p is the smallest prime factor of k · p.

linear_sieve(n):
    smallest_prime_factor := array of length n+1, init 0
    primes := []
    for i in 2..n:
        if smallest_prime_factor[i] == 0:
            smallest_prime_factor[i] = i
            primes.append(i)
        for p in primes:
            if p > smallest_prime_factor[i] or p * i > n:
                break
            smallest_prime_factor[p * i] = p
    return primes

For each i, the inner loop walks the primes p in increasing order, marking p * i for each. The key: stop as soon as p > smallest_prime_factor[i], because if p > spf[i], then spf[p · i] = spf[i] < p, and marking p · i here would be a duplicate (it will be marked when the outer loop reaches i' = (p · i) / spf[i]). The early exit ensures each composite is marked exactly once, giving O(n) total work.

The linear sieve also delivers, as a free byproduct, the smallest prime factor of every integer up to n — which is useful for instant prime factorization queries: factor k by repeatedly dividing by smallest_prime_factor[k] until k = 1. See Linear Sieve (planned) for full treatment.

In practice, the O(n) bound does not translate into a speed win. The cp-algorithms linear-sieve article is blunt about this: “the difference between them is not so big. In practice the linear sieve runs about as fast as a typical implementation of the sieve of Eratosthenes,” and “in comparison to optimized versions of the sieve of Eratosthenes, e.g. the segmented sieve, it is much slower” (cp-algorithms, Linear Sieve). The reasons are constant-factor: the linear sieve needs an lp[] array of n integers (not bits) plus a list of primes (≈ n / ln n entries), so it touches far more memory with a less cache-friendly access pattern than a bit-packed Eratosthenes. The linear sieve shines when you need the smallest-prime-factor table as a byproduct — for instant O(log k) factorization — not when you only want the primes. See Linear Sieve for the full treatment.

5.5 Sieve of Atkin

The Sieve of Atkin (Atkin and Bernstein, 2003) is a more elaborate sieve that enumerates primes in O(n / log log n) time — asymptotically faster than Eratosthenes by a log log n factor. It uses quadratic forms (the number of solutions to equations like 4x² + y² = k) to identify candidate primes, rather than crossing out multiples. The theoretical speedup is genuine but small: log log n is ~3–4 for any human-scale input, so Atkin’s edge is at most a single-digit constant factor in the limit.

In practice this asymptotic advantage never materializes at attainable input sizes. Atkin’s per-candidate work has a much larger constant factor and a less cache-friendly access pattern than a well-engineered Eratosthenes sieve. The authoritative high-performance sieve, Kim Walisch’s primesieve, deliberately uses a segmented Sieve of Eratosthenes with wheel factorization — not Atkin — and sieves all the way up to 2⁶⁴, generating the 50,847,534 primes below 10⁹ in about 0.4 s on a single 2.66 GHz core, roughly 50× faster than an ordinary textbook Eratosthenes (per the primesieve documentation). The commonly cited crossover at which Atkin’s log log n advantage would overtake an equally optimized Eratosthenes sits around n ≈ 10^10, by which point the dominant constraint is memory (a full bit-sieve of 10^10 is already ~1.25 GB), so the segmented Eratosthenes — whose memory is O(√n + S) — wins on every axis that matters in practice. The takeaway: Atkin is a beautiful number-theoretic result of limited engineering relevance; reach for optimized Eratosthenes.

6. Why It Works — Correctness

Claim. After the sieve runs, is_prime[i] is True iff i is prime.

Proof. We show two directions.

(⇒) If i is composite, is_prime[i] is False. Write i = a · b with 1 < a ≤ b < i. Then a ≤ √i ≤ √n. So a has a smallest prime factor q ≤ a ≤ √n. The outer loop visits q before visiting i. When the outer loop is at q, is_prime[q] is True (we’ve visited only primes smaller than q so far, and a prime can’t be marked composite by smaller primes). The inner loop then marks every multiple of q from q² onward. Since i = (i/q) · q ≥ q² (because q ≤ √i ≤ √n implies i ≥ q²), i is in the inner loop’s range and gets marked.

(⇐) If i is prime, is_prime[i] is True. The only writes to is_prime[k] happen in the inner loop, where k is a multiple of some p ≥ 2. A prime is divisible only by itself and 1, so the only p for which i is a multiple is p = i. But the inner loop starts at p² = i² > i (for i ≥ 2), so i itself is not marked. is_prime[i] retains its initial value True.

The sieve is therefore correct. The complexity argument from §4 caps the runtime.

7. Pitfalls

7.1 Indexing 0 and 1

By definition, 0 and 1 are not prime (1 is the unit; primality is reserved for integers ≥ 2). The boolean array must mark them False explicitly, or the final list will include 0 and 1 erroneously. Many homemade sieves ship with this bug.

7.2 Inner Loop Starting at 2p Instead of p²

A correctness-preserving but slow choice. Starting from 2p makes the algorithm O(n log n) instead of O(n log log n) — still fast, but a measurable factor of log n / log log n ≈ 3-4 for typical inputs. Always start from p².

7.3 Overflow on p * p for Very Large n

If n approaches the maximum signed 32-bit integer (~2·10^9), then p ≤ √n ≈ 46341 and p * p fits in 32 bits. But for 64-bit n ≈ 10^18, p can be up to ~10^9, and p * p overflows 32-bit arithmetic (though 64-bit is fine). Use the appropriate integer width. Python is overflow-free.

7.4 Memory Blow-Up in Naive Implementations

[True] * (n+1) in Python allocates n+1 Python objects, each 28+ bytes — for n = 10^8 that’s >2.5 GB. Use bytearray or numpy boolean arrays for memory-efficient sieves. The C-level boolean array is 1 byte per entry; a bit-packed array is 1 bit per entry (8× denser, but trickier to access).

7.5 Forgetting to Mark Composites Before the Final Reading Loop

A common bug in incremental sieves: yielding i as prime as soon as the outer loop reaches it. This is correct only if the mark loop has already eliminated every composite ≤ i — which it has, in the standard sieve (the mark loop for prime p runs to completion before the outer p increments). Streaming variants need to be careful about ordering.

7.6 Using <= sqrt(n) with Floating-Point sqrt

int(math.sqrt(n)) can be off-by-one due to floating-point rounding for large n. Use math.isqrt(n) (Python 3.8+) which returns the integer square root exactly. Or just use the condition p * p <= n directly — it sidesteps sqrt entirely.

7.7 The “Off-By-One in Range” Bug

Sieving up to n means including n itself in the array. range(0, n) excludes n; range(0, n+1) includes it. [True] * (n+1) creates n+1 slots indexed 0..n. Off-by-one bugs here are endemic.

7.8 Incorrectly Treating 0 and 1 in Counting Problems

Problems like “count primes less than n” (LeetCode 204) want strictly less than n. Sieving up to n - 1 (or sieving up to n and not counting index n) is the right answer. Read the problem statement carefully: “less than” vs “less than or equal” matters.

7.9 Sieve Range Doesn’t Need to Start at 2

For “count primes in [L, R]” with very large R, a basic sieve up to R may not fit in memory. Use the segmented sieve (§5.3), or use the Meissel–Mertens–Lehmer prime-counting algorithm if you only need the count.

8. Diagram — How Composites Get Marked

flowchart TD
  A["Init: is_prime[2..n] = True"] --> B{p² ≤ n?}
  B -->|yes| C{is_prime[p]?}
  C -->|yes| D["Mark p², p²+p, p²+2p, ... ≤ n as composite"]
  D --> E["p ← p + 1"]
  C -->|no| E
  E --> B
  B -->|no| F["Read all i with is_prime[i]=True as primes"]

What this diagram shows. The control flow of Eratosthenes’ sieve. The outer loop walks p from 2 upward. At each p, we check whether p² still fits in our range — if not, every composite has already been marked by a prime ≤ √n. If p is unmarked (i.e., still prime), we run the inner mark loop starting at p² and stepping by p. The early-stop condition p² > n is what gives the algorithm its O(√n) outer-loop iterations and O(n log log n) total cost. Skipping marked p (composites) is a small optimization — the inner loop wouldn’t do harm there but would waste time re-marking already-marked composites.

9. Common Interview Problems

ProblemLeetCode # / SourceConnection
Count PrimesLC 204Standard sieve up to n
Closest Prime Numbers in RangeLC 2523Segmented sieve over [L, R]
Prime in DiagonalLC 2596Per-element primality on bounded values
Number of Subarrays with Bounded Maximumn/aSliding window after sieve
Sum of Primes ≤ ncompetitive programmingSieve + sum
Smallest Prime Factor of Each Integer ≤ ncompetitive programmingLinear sieve byproduct
Largest Prime Factor of nLC / Project Euler 3Trial division up to √n; sieve for bulk
Goldbach Conjecture Verificationcompetitive programmingSieve up to n, then test pairs
Twin Primes Countingcompetitive programmingSieve, then scan adjacent primes
Primes in a Polynomial Sequencecompetitive programmingSieve-then-filter
Distinct Prime Factors of nLC 2521Sieve-based factorization
Sum of Three or FiveProject Euler 1Inclusion-exclusion or sieve
RSA setup (find large primes)crypto courseworkRandom + Miller-Rabin (NOT sieve — primes too large)

The core competitive-programming idiom: precompute primes up to a bound, then answer each query in O(log n) or O(1). For n ≤ 10^7, sieve and store; for n ≤ 10^11, segmented sieve; beyond that, individual primality testing per query.

10. Variants

10.1 Sieve of Sundaram

Pritchard 1981 (originally Sundaram 1934) describes a different sieve that finds odd primes by eliminating numbers of the form i + j + 2ij. Complexity O(n log n) — slower than Eratosthenes — but it is sometimes presented in textbooks as an alternative formulation. Not recommended in practice; it appears more as a curiosity.

10.2 Sieve for Smooth Numbers

A modification of Eratosthenes that marks numbers with all prime factors ≤ B (B-smooth numbers). Used in factoring algorithms like the Quadratic Sieve and General Number Field Sieve to find smooth quadratic residues. The same O(n log log B) framework applies.

10.3 Primes in Arithmetic Progressions

To find primes p ≡ a (mod q) up to n, sieve normally and filter — there is no faster sieve for this restricted question because Dirichlet’s theorem on primes in arithmetic progressions doesn’t improve the constant.

10.4 Multiplicative-Function Sieves

The linear sieve generalizes to compute any multiplicative function f(n) (a function with f(a·b) = f(a)·f(b) for coprime a, b) in O(n) time: Euler totient φ, Möbius μ, divisor function d(n), sigma function σ(n). Sweep i from 2 to n; if i is prime, set f(i) directly; otherwise compute f(p · m) from f(m) using the multiplicative recurrence.

11. Open Questions

  • Resolved (§5.5): there is no practically relevant crossover. Optimized Eratosthenes (wheel factorization + segmentation, as in primesieve) wins up to and beyond n = 10^10, by which point memory, not asymptotic operation count, is the binding constraint. Atkin’s log log n advantage is real only in the asymptotic limit and is swamped by its constant factor at all attainable inputs.
  • Can the sieve be parallelized usefully? The mark loops for distinct primes are independent in principle, but they all write to the same boolean array — cache contention dominates. The segmented sieve parallelizes naturally across segments, achieving near-linear speedup with thread count for the segmented part. Library primesieve does this.
  • Are there primality questions that fundamentally require a sieve rather than a per-integer test? Yes — anything asking for “all primes in an interval” or “the k-th prime” is most efficient with a sieve up to that point; per-integer tests require knowing where to stop.

12. See Also

Graph View

Backlinks