🔢 Sieve of Eratosthenes

Invented around 240 BC by the ancient Greek mathematician Eratosthenes, this algorithm finds all primes up to a limit N. Starting from 2, it marks all multiples of each prime as composite — any number that survives unmarked is prime. Watch the pattern emerge: primes glow gold, composites dim, and you can see the Ulam spiral of primes and the prime gaps grow. The prime counting function π(x) ≈ x/ln(x) is shown below. 🇺🇦 Українська

View

Current p—
Primes found0
π(N)—
N / ln(N) approx—
Largest prime gap—

The Prime Number Theorem

The Prime Number Theorem (1896, Hadamard & de la Vallée Poussin) states that π(x) ~ x/ln(x) as x → ∞. A sharper approximation is the logarithmic integral li(x) = ∫₂ˣ dt/ln(t). The sieve runs in O(N log log N) time — remarkably fast. The twin prime conjecture asks whether there are infinitely many primes p where p+2 is also prime; this remains unproven. The Riemann Hypothesis predicts the exact error term in π(x).

About the Sieve of Eratosthenes

This simulation implements the classic Sieve of Eratosthenes (c. 240 BC) directly: starting from an all-true boolean array over 2…N, it repeatedly finds the next unmarked index p, and — only once p² ≤ N — marks every multiple of p from p² upward as composite, skipping already-eliminated numbers. Everything left unmarked when the sieve finishes is prime. Each animation step performs one such marking pass and redraws the grid (or the Ulam spiral, which winds the integers 1…N outward from the centre) with primes in gold and the currently active p in orange. A second panel plots the running prime-counting function π(x) — the number of primes found so far — against the classical estimate x/ln(x), letting you watch the Prime Number Theorem emerge as N grows.

🔬 What it Shows

A live boolean sieve over integers 2 to N (up to 10,000): unmarked survivors are prime, and multiples of each newly-found prime p are struck out starting at p² (smaller multiples were already struck out by smaller primes). The plot below the grid compares the actual count π(x) against x/ln(x), the Prime Number Theorem's asymptotic estimate.

🎮 How to Use It

Drag Limit N to choose how many integers to sieve and Anim speed to control steps per frame. Switch between the Grid layout and the Ulam Spiral with the view buttons. Press Start to animate the sieve step by step, Instant to solve immediately, or Reset to rebuild the array from scratch.

💡 Did You Know?

The sieve only needs to test candidate primes p up to √N, and each is skipped if it was already marked composite by a smaller prime — this is why its running time is a remarkably efficient O(N log log N), one of the fastest known ways to enumerate all primes below a bound.

Frequently asked questions

Why does marking only start at p² instead of 2p?

Any composite multiple of p smaller than p² — such as 2p, 3p, …, (p−1)p — already has a prime factor smaller than p, so it was struck out during an earlier pass when that smaller prime was processed. Starting each pass at p² skips redundant work and is the key optimization that gives the sieve its O(N log log N) running time instead of a slower O(N log N).

How does the Ulam spiral relate to this sieve?

The Ulam spiral view takes exactly the same sieve array used in the grid view and re-plots each surviving prime along a square spiral path that winds outward from the centre, one cell per integer. Visually, primes tend to cluster along certain diagonal lines in this layout — a striking, still not fully explained pattern first noticed by mathematician Stanisław Ulam in 1963 while doodling during a boring conference talk.

What does the π(x) versus x/ln(x) plot mean?

π(x) is the prime-counting function: the actual number of primes less than or equal to x, tallied directly from the sieve as it runs. x/ln(x) is the leading-order asymptotic approximation from the Prime Number Theorem (proved independently by Hadamard and de la Vallée Poussin in 1896). The two curves track each other increasingly closely as N grows, which is exactly what the theorem predicts — though the ratio only converges to 1 in the limit x → ∞.

Why does the sieve run in O(N log log N) time?

The total work is proportional to N times the sum of 1/p over all primes p ≤ √N (one "hit" per multiple of each prime). By Mertens' second theorem, the sum of reciprocals of primes up to a bound grows like log log of that bound, so total work scales as N·log log N — asymptotically close to linear and far faster than trial-dividing every number individually.

What is the largest prime gap statistic tracking?

It reports the largest difference between consecutive primes found up to the current limit N (for example, the gap of 8 between 89 and 97). Prime gaps grow irregularly but on average widen like ln(N) as N increases, per the Prime Number Theorem; the Cramér conjecture proposes a tighter bound on how large any individual gap can get, but it remains unproven.

Does this sieve prove or disprove the twin prime conjecture?

No — the sieve can enumerate every twin prime pair (p, p+2) below whatever limit N you choose, but that only ever confirms finitely many examples. The twin prime conjecture claims infinitely many such pairs exist, which is a statement about all primes, not a finite computation; despite strong numerical and partial theoretical evidence (including Zhang's 2013 bounded-gaps breakthrough), it remains an open problem in number theory.