Sieve of Eratosthenes
The Sieve of Eratosthenes is the oldest way to list the prime numbers. Write down the numbers from 2 to N. Take the first number that is not crossed out: it is prime. Cross out all its multiples, then take the next number that is left. Here every prime crosses out its multiples in its own colour, so you can see which prime removed which number. Press Play to watch each prime cross out its multiples, or Step to do one prime at a time. The numbers that are left are the primes.
How it works
- Choose how far to sieve: up to 100, 200, 500 or 1000.
- Press Play to watch the sieve run, or Step to finish one prime at a time. Space and the right arrow key work as well.
- Change the speed, or switch the numbers, the current prime, the p² start and the prime count on or off. Save the grid as a PNG with the Save button.
Why start at p²?
When the sieve reaches a prime p, every smaller multiple of p, such as 2p or 3p, has already been crossed out by a smaller prime. The first multiple that is still left is p × p. That is why the dashed box marks p², and why the sieve can stop as soon as p² is more than N: every number that is left is then prime.
Colours
Each prime gets its own colour. A crossed-out number keeps the colour of its smallest prime factor, the prime that crossed it out first. When a prime reaches a number that is already crossed out, the number flashes but keeps its colour. So 12 stays the colour of 2, even though 3 visits it too.
Frequently asked questions
How many primes are there up to 100?
There are 25 primes up to 100, 46 up to 200, 95 up to 500 and 168 up to 1000.
Why is 1 not crossed out or coloured?
1 is not a prime number and not a composite number either, so the sieve starts at 2. 1 is shown greyed out.
Is it free?
Yes. The Sieve of Eratosthenes runs free in your browser and needs no sign-up.
Related tools
About the Sieve of Eratosthenes - the oldest prime sieve
Who Eratosthenes was, how his sieve finds every prime up to N, why it only needs primes up to the square root of N and how fast it is. Then try the animated sieve.
Ulam spiral
Draw the Ulam spiral in your browser. Mark the primes, read the quadratic on each diagonal, and open Euler's unbroken run of 40 primes.
The Ulam spiral
How Stanisław Ulam's 1963 spiral lays the integers on a square grid, why primes gather on quadratic diagonals, and where Euler's forty primes sit when the spiral starts at 41.
The Collatz Conjecture
Explore the Collatz 3n+1 problem in your browser. Walk hailstone sequences, grow a geometric Collatz tree, and zoom the continuous Collatz fractal.
Multiplication Circles
Join each number on a circle to its multiple. Draw a times table, a cardioid, or a string figure on paper, chalk, or wood.
Buffon's Needle
Drop needles on a lined floor in your browser. Count the crossings and watch Buffon's 1777 experiment estimate π.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor