Introduction

Around 240 BC, the Greek polymath Eratosthenes of Cyrene wrote down a recipe for finding every prime up to some limit nn. Start with all integers from 2 to nn. 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(nlog⁡n)O(n \log n), and can a cleverer version reach true O(n)O(n)? And why do primes matter so much that engineers still spend microseconds optimizing this 2,200-year-old recipe?

Cross Out the Multiples

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">Watch the Sieve of Eratosthenes in action. The smallest unmarked number is always prime — the sieve crosses out all its multiples. Step through it one prime at a time or run it to completion.</p>
<div id="controls" class="btns">
  <button id="stepBtn" type="button">Step</button>
  <button id="runBtn" type="button">Run</button>
  <button id="resetBtn" type="button" class="ghost">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">prime</span>
  <span class="leg-crossed">composite</span>
  <span class="leg-current">current prime</span>
  <span class="leg-unmarked">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Sieve of Eratosthenes demo — linear-sieve style (smallest prime factor)
// Complexity: O(n log log n) for the classic sieve displayed here.
// Each step: pick the smallest unmarked number (it's prime), mark all its
// multiples as composite. We stop at sqrt(N) for marking; remaining unmarked numbers are already prime.
const N = 100;
// state[i]: 'unmarked' | 'prime' | 'current' | 'crossed'
let state = [];
let nextPrime = 2;   // next prime to sieve
let done = false;
let runTimer = null;
let primeCount = 0;

function init() {
  state = Array(N + 1).fill('unmarked');
  state[0] = state[1] = 'crossed'; // 0 and 1 are not prime
  nextPrime = 2;
  done = false;
  primeCount = 0;
  if (runTimer) { clearInterval(runTimer); runTimer = null; }
  document.getElementById('stepBtn').disabled = false;
  document.getElementById('runBtn').disabled = false;
  setInfo('Click Step to start.', '');
  render();
}

function render() {
  const g = document.getElementById('grid');
  g.innerHTML = '';
  for (let i = 1; i <= N; i++) {
    const d = document.createElement('div');
    d.className = 'cell ' + state[i];
    d.textContent = i;
    g.appendChild(d);
  }
  document.getElementById('count').textContent =
    primeCount > 0 ? fmt('%primeCount% prime%v% found', { primeCount: primeCount, v: primeCount > 1 ? 's' : '' }) : '';
}

function setInfo(msg, cnt) {
  document.getElementById('info').textContent = msg;
  if (cnt !== undefined) document.getElementById('count').textContent = cnt;
}

function step() {
  if (done) return;

  // Finalize the previous "current" prime — mark it as prime
  for (let i = 2; i <= N; i++) {
    if (state[i] === 'current') { state[i] = 'prime'; primeCount++; }
  }

  // Find next unmarked
  while (nextPrime <= N && state[nextPrime] !== 'unmarked') nextPrime++;

  if (nextPrime > N) {
    // Any remaining unmarked numbers are prime (they survived all sieves)
    for (let i = 2; i <= N; i++) {
      if (state[i] === 'unmarked') { state[i] = 'prime'; primeCount++; }
    }
    done = true;
    if (runTimer) { clearInterval(runTimer); runTimer = null; }
    document.getElementById('stepBtn').disabled = true;
    document.getElementById('runBtn').disabled = true;
    setInfo(fmt('Done! All primes up to %N% found.', { N: N }), fmt('%primeCount% primes found', { primeCount: primeCount }));
    render();
    return;
  }

  const p = nextPrime;
  state[p] = 'current';
  // Cross out multiples of p (start at p*p — smaller multiples already crossed)
  let crossed = 0;
  for (let m = p * p; m <= N; m += p) {
    if (state[m] === 'unmarked') { state[m] = 'crossed'; crossed++; }
  }
  // Also cross any multiples < p*p that may be unmarked (only relevant for first few primes)
  for (let m = p * 2; m < p * p && m <= N; m += p) {
    if (state[m] === 'unmarked') { state[m] = 'crossed'; crossed++; }
  }
  nextPrime = p + 1;
  setInfo(fmt('Prime %p% — crossed out %crossed% new composite%v%.', { p: p, crossed: crossed, v: crossed !== 1 ? 's' : '' }), '');
  render();
}

function run() {
  document.getElementById('stepBtn').disabled = true;
  document.getElementById('runBtn').disabled = true;
  runTimer = setInterval(() => { step(); if (done) clearInterval(runTimer); }, 300);
}

document.getElementById('stepBtn').addEventListener('click', step);
document.getElementById('runBtn').addEventListener('click', run);
document.getElementById('resetBtn').addEventListener('click', init);

// Verify: after full sieve, primes up to 100 should be 25
// This is checked in STEP 3 externally.
init();
Result
Console

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.

The Real Complexity

How fast is the sieve, really?

  • Classic sieve — O(nlog⁡log⁡n)O(n \log \log n): when the sieve crosses out multiples of a prime pp, it does roughly n/pn/p operations. Summing over all primes up to nn gives n⋅∑p≤n1/pn \cdot \sum_{p \le n} 1/p. That sum grows like log⁡log⁡n\log \log n — one of the slowest-growing functions in mathematics — so the total work is O(nlog⁡log⁡n)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 mm is crossed out exactly once, by its smallest prime factor. Total work: exactly O(n)O(n).
  • Space vs time: both variants use O(n)O(n) space for the boolean array. Segmented sieves reduce this to O(n)O(\sqrt{n}) by processing the range in blocks, making them cache-friendly for very large nn.
  • Lower bound: any sieve-style algorithm must at minimum read the output — π(n)≈n/ln⁡n\pi(n) \approx n / \ln n primes — so O(n)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 nn in the billions. Unlike the open questions behind P vs NP or factoring, the complexity of prime generation is fully understood.

Where It Matters

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)O(\log n) factorization for any number up to nn — 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 π(n)\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)O(\log n) factorization, and a clean example of how a near-optimal algorithm can survive unchanged for over two millennia.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sieve-of-eratosthenes/Content licensed under CC BY-NC 4.0.