The Oldest Algorithm
The Sieve of Eratosthenes, devised over two millennia ago, remains one of the most elegant algorithms in mathematics. The idea is breathtakingly simple: write down all numbers from 2 to N, then starting from 2, cross off every multiple. The first uncrossed number after each round is the next prime. Repeat until you have sieved past √N, and every surviving number is guaranteed prime. This simulation lets you watch the crossing-off process unfold in real time on a color-coded grid.
Why It Works
Every composite number has at least one prime factor no greater than its square root. By the time the sieve has processed all primes up to √N, every composite up to N has been marked at least once. This is why the sieve's outer loop only needs to run up to √N — a fact that makes the algorithm remarkably efficient at O(N log log N), near-linear in the size of the input range.
Patterns in the Grid
Watch the grid carefully and you will notice striking visual patterns. Multiples of 2 form every other cell — a checkerboard. Multiples of 3 create diagonal stripes depending on the column count. As higher primes are sieved, the pattern becomes increasingly irregular, reflecting the pseudo-random distribution of primes. Twin primes (pairs like 11,13 or 29,31) appear as adjacent survivors, growing rarer but never provably vanishing.
From Ancient Greece to Modern Cryptography
The primes discovered by this sieve are the foundation of RSA encryption, which secures internet commerce. While Eratosthenes used the sieve to study pure number theory, today's variants — segmented sieves, wheel sieves, and the Sieve of Atkin — generate primes at industrial scale. The fundamental insight remains unchanged: elimination by multiplication is the fastest path to discovering primes.