Sieve of Eratosthenes

Around 240 BC, the Greek polymath Eratosthenes of Cyrene wrote down a recipe for finding every prime up to some limit $n$. Start with all integers from 2 to $n$. The smallest unmarked number must be prime — because nothing smaller divided it. Cross out all of its multiples. Repeat. What survives is exactly the primes.

The elegance is hard to improve on: you never divide, you never test primality — you only count and cross out. It is one of the oldest algorithms in existence, and modern computers still use variants of it to generate prime tables millions of entries long in fractions of a second.

But beneath the simplicity lies a fascinating complexity story. How many crossings-out do you actually do? Why is the classic sieve slightly better than $O(n \log n)$, and can a cleverer version reach true $O(n)$? And why do primes matter so much that engineers still spend microseconds optimizing this 2,200-year-old recipe?

Every number starts unmarked. The smallest unmarked one is always prime. Click Step to advance the sieve one prime at a time — watch it cross out that prime's multiples. Or press Run to finish automatically.

<p class="hint">{{hint}}</p>
<div id="controls" class="btns">
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="info-row">
  <span class="info" id="info">{{click_step_to_start}}</span>
  <span class="count" id="count"></span>
</div>
<div id="grid" class="grid"></div>
<div class="legend">
  <span class="leg-prime">{{leg_prime}}</span>
  <span class="leg-crossed">{{leg_composite}}</span>
  <span class="leg-current">{{leg_current_prime}}</span>
  <span class="leg-unmarked">{{leg_unmarked}}</span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .55rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.info-row { display: flex; align-items: baseline; gap: .7rem; margin-bottom: .4rem; min-height: 1.4em; }
.info { font-size: .95rem; font-weight: 600; color: #1d3557; }
.count { font-size: .85rem; color: #555; }
.grid { display: grid; grid-template-columns: repeat(10, 1fr); gap: 4px; }
.cell { width: 100%; aspect-ratio: 1; display: flex; align-items: center;
        justify-content: center; font: 600 13px ui-monospace, monospace;
        border-radius: 6px; border: 1px solid #cdd9e3; background: #e8eef3;
        color: #333; transition: background .2s, color .2s; }
.cell.unmarked { background: #e8eef3; color: #333; border-color: #cdd9e3; }
.cell.prime   { background: #1d3557; color: #fff; border-color: #1d3557; }
.cell.current { background: #e63946; color: #fff; border-color: #c92f3c; }
.cell.crossed { background: #c9ccd1; color: #888; border-color: #adb1b8; text-decoration: line-through; }
.cell.skip    { background: transparent; border-color: transparent; color: transparent; }
.legend { display: flex; gap: .7rem; flex-wrap: wrap; margin-top: .5rem; font-size: .8rem; }
.legend span { display: flex; align-items: center; gap: .3rem; }
.legend span::before { content: ""; display: inline-block; width: 12px; height: 12px; border-radius: 3px; }
.leg-prime::before    { background: #1d3557; }
.leg-crossed::before  { background: #c9ccd1; }
.leg-current::before  { background: #e63946; }
.leg-unmarked::before { background: #e8eef3; border: 1px solid #cdd9e3; }

// Code not found

Notice what the sieve never does: it never divides, never tests whether a number is divisible by anything. It only adds — jumping ahead by the prime's own size each time. A composite number gets crossed out the first time its smallest prime factor reaches it. That is why the linear sieve works: each composite is eliminated exactly once.

How fast is the sieve, really?

• Classic sieve — $O(n \log \log n)$: when the sieve crosses out multiples of a prime $p$, it does roughly $n/p$ operations. Summing over all primes up to $n$ gives $n \cdot \sum_{p \le n} 1/p$. That sum grows like $\log \log n$ — one of the slowest-growing functions in mathematics — so the total work is $O(n \log \log n)$, barely more than linear.
• Can we do better? Yes — the linear sieve: the classic sieve crosses out some composites more than once (12 is eliminated by both 2 and 3). The linear sieve (Euler's sieve, refined by Atkin and others) keeps a smallest-prime-factor (SPF) table: each composite $m$ is crossed out exactly once, by its smallest prime factor. Total work: exactly $O(n)$.
• Space vs time: both variants use $O(n)$ space for the boolean array. Segmented sieves reduce this to $O(\sqrt{n})$ by processing the range in blocks, making them cache-friendly for very large $n$.
• Lower bound: any sieve-style algorithm must at minimum read the output — $\pi(n) \approx n / \ln n$ primes — so $O(n)$ is essentially optimal for dense prime generation.

The result is a solved, classical problem: the linear sieve is provably optimal in work, and segmented variants keep it practical for $n$ in the billions. Unlike the open questions behind P vs NP or factoring, the complexity of prime generation is fully understood.

Generating primes quickly is not an academic exercise — it underpins a surprising slice of modern computing:

• Cryptography: RSA and other public-key systems rely on large primes. Sieving is the standard first pass for finding prime candidates before a probabilistic primality test confirms them.
• Smallest-prime-factor tables: the linear sieve builds an SPF array as a side-effect, giving $O(\log n)$ factorization for any number up to $n$ — useful for factoring billions of numbers offline.
• Number theory and research: sieves produce the raw data behind the Riemann hypothesis investigations, twin-prime searches, and distribution statistics for $\pi(n)$.
• Competitive programming: a precomputed prime table or SPF array is one of the most common setup steps in contest solutions — fast, deterministic, and easy to reason about.
• Algorithm education: the sieve is a textbook showcase for amortized analysis, cache behavior, and the difference between worst-case and average-case complexity.

Master the sieve and you hold the key to fast prime generation, $O(\log n)$ factorization, and a clean example of how a near-optimal algorithm can survive unchanged for over two millennia.

The Sieve of Eratosthenes is a rare gift in computer science: a problem that is both completely solved and endlessly instructive. Eratosthenes described the crossing-out idea in 240 BC; twenty-three centuries of refinement led to the linear sieve, which matches the information-theoretic lower bound and cannot be meaningfully improved.

Along the way the sieve teaches amortized complexity through the harmonic series, cache-aware design through segmented variants, and the power of precomputation through smallest-prime-factor tables. It even links, indirectly, to the deepest open question in mathematics — the Riemann hypothesis is essentially a conjecture about how precisely the sieve's output matches the logarithmic integral.

Eratosthenes crossed out numbers with a stylus on a wax tablet. Modern CPUs cross out bits in L1 cache at billions of operations per second. The algorithm is the same.