Count Primes
Sieve of Eratosthenes
time O(n log log n)space O(n)
Instead of testing each number for primality one by one, the sieve starts every number unmarked and, for each prime it finds, crosses out all of that prime's multiples in one sweep — anything still unmarked at the end must be prime.
Details
Animated on: n = 10 — count how many primes are strictly less than n.
Problem:Count PrimesMedium
Sieve of Eratosthenes
step 1 / 11
2
[0]3
[1]4
[2]5
[3]6
[4]7
[5]8
[6]9
[7]Sieve of Eratosthenes: numbers 2..9 start unmarked; cross out every multiple of each prime found.
Pseudocode
1FUNCTION countPrimes(n):2 mark every number 0..n-1 as prime to start3 FOR i from 2 to sqrt(n):4 IF i is still marked prime:5 mark every multiple of i as composite6 RETURN how many numbers below n are still prime
← / → step · space play · Home restart
Every step in words
Show all 11 steps
- Sieve of Eratosthenes: numbers 2..9 start unmarked; cross out every multiple of each prime found.
- 2 is prime (still unmarked).
- Mark 2's multiples composite: 4, 6, 8.
- 3 is prime (still unmarked).
- Mark 3's multiples composite: 6 (already marked), 9.
- 4 is already marked composite — skip.
- 5 is prime; its next multiple would be 10, which is out of range.
- 6 is already marked composite — skip.
- 7 is prime; its next multiple would be 14, out of range.
- 8 and 9 are already marked composite — skip.
- Unmarked numbers less than 10: 2, 3, 5, 7 → count = 4.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.