Interactive Sieve of Eratosthenes
Press 'Start' to begin the visualization.
Performance Stats
| Algorithm | Operations | Time Elapsed |
|---|
What is This?
The Sieve of Eratosthenes is a highly efficient ancient algorithm for finding all prime numbers up to a specified limit. Instead of testing each number for primality, it works by progressively marking as "composite" (not prime) the multiples of each prime, starting with 2.
Legend
- Default: Number is currently assumed to be prime.
- Current Prime: The prime number we are using to "sieve" with.
- Sieving: A number being marked as a multiple (it will turn gray).
- Composite: Confirmed not to be prime.
- Prime: Confirmed to be a prime number.
Key Optimizations
We only need to find primes and sieve their multiples up to the square root of the limit. Any composite number larger than that must have a prime factor smaller than the square root, which we would have already processed.
p * p <= limit
When sieving for a prime `p`, we can start marking multiples from p * p. Any smaller multiple (like `2*p` or `3*p`) would have already been marked by the smaller primes (2 or 3).
for (let i = p*p; ...)