Sieve of Eratosthenes Screensaver
The Sieve of Eratosthenes screensaver runs the real, 2,200-year-old prime-finding algorithm live, crossing out multiples of each prime as it discovers them. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Sieve of Eratosthenes screensaver works
The saver lays out a real grid of numbers up to a set limit, then runs the true Sieve of Eratosthenes over it.
Starting from 2, every real multiple of the current prime is crossed out, and the next uncrossed number becomes the next real prime found.
The process repeats live, crossing out multiples of 3, then 5, then 7, and so on, exactly as the real ancient algorithm defines.
Once every number up to the limit is resolved as prime or composite, it holds briefly, then a fresh sieve begins with a new limit.
Eratosthenes and the art of crossing out
Eratosthenes of Cyrene was a Greek scholar of the third century BC who became chief librarian at the Library of Alexandria and is better known for estimating the circumference of the Earth. The sieve that carries his name is a method of finding all primes up to a limit without dividing one number by another. The earliest known written account is in Nicomachus of Gerasa’s Introduction to Arithmetic, from the early second century AD, which credits Eratosthenes.
The trick is to work from the primes outwards. Start with 2 and cross out its multiples; the next number not crossed out must be prime, so cross out its multiples too, and continue. Anything left standing at the end is prime. A useful refinement is to start crossing out from the square of each prime, since smaller multiples have already been struck by a smaller prime, and to stop once the square of the current prime exceeds the limit.
In modern terms the sieve runs in time proportional to n log log n, which is nearly linear, although the basic version needs memory for every number up to the limit. A segmented sieve handles large ranges in chunks, which cuts the memory needed to about the square root of the limit while keeping the same running time.
A worked example
Once 2 is found prime, every even number lights up as composite in one pass; then 3 clears most remaining multiples of three, and the sieve quickly narrows in on the real remaining primes.
Settings & tips
- Accent recolours the prime currently sieving.
- This is the real, unmodified ancient sieve algorithm, not an approximation.
- A fresh sieve begins automatically once every number is resolved.
Frequently asked questions
- Is this a real prime-finding algorithm?
- Yes — the real Sieve of Eratosthenes, a genuine algorithm dating back over two thousand years.
- Why cross out multiples instead of testing each number?
- It is real and provably faster: crossing out multiples finds every prime up to the limit without ever dividing.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- Why start crossing out from the square of the prime?
- Every smaller multiple of a prime p has a smaller prime factor, so it has already been crossed out earlier. The first new number struck by p is p times p.
- When does the sieve stop?
- As soon as the square of the current prime exceeds the limit, since any composite number up to the limit must have a prime factor no larger than its square root.
- Is this how computers find huge primes?
- Not for the very large ones used in cryptography. Those are found with probabilistic primality tests, while the sieve suits listing every prime in a moderate range.