Number theory · Prime numbers
Sieve of Eratosthenes
Enter a number and watch every prime up to it appear, one step at a time.
Step by step
Step 0–Current prime p
0Primes found
0Crossed out
0Still unmarked
The sieve
Key
Not yet decided
Prime
Crossed out by the current prime
Crossed out earlier
Being examined
The method
- List every whole number from 2 to n. The number 1 is left out because it is not prime.
- Let p = 2, the first prime.
- Cross out the multiples of p, starting at p² and counting up in steps of p.
- Move p to the next number that is still unmarked. It is prime, because no smaller prime divides it.
- Repeat while p² ≤ n. Once p² is larger than n, stop: every number still unmarked is prime.
The rule
Cross out multiples of each prime p:
start at p × p
— and —
stop once p × p > n
— and —
stop once p × p > n
Any multiple smaller than p², such as 3 × p, has a smaller prime factor and was crossed out earlier. Every composite number up to n has a prime factor no larger than √n.
Your sieve
Only these primes cross anything out. Every other prime survives without being used.