Pattern visualizer
Count Primes
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. Animated on: n = 10 — count how many primes are strictly less than n..
Sieve of Eratosthenes
time O(n log log n)space O(n)step 1 / 11
2
[0]3
[1]4
[2]5
[3]6
[4]7
[5]8
[6]9
[7]line 2
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