Sieve of Eratosthenes Visualizer
Watch prime numbers emerge as composite numbers are filtered out across an interactive 1 to 100 grid. Use the controls to play, pause, or step through the process.
Click “Start Animation” or “Next Step” to begin crossing out composite numbers up to the square root of 100 (which is 10).
The Square Root Cutoff Rule (√N Limit)
Why does the Sieve of Eratosthenes never need to test primes larger than the square root of your limit (√N)? Every composite number can be split into two factors: a × b. Both factors cannot be bigger than the square root, because multiplying them would produce a number larger than your limit. Therefore, at least one factor must be less than or equal to the square root. Once you check primes up to the square root, you are done!
02. Prime Multiples Eliminator & Skip-Order Checker
See how any chosen prime p crosses out multiples up to limit N. Notice how multiples smaller than p² are skipped because a smaller prime already crossed them out:
03. Sieve Cutoff & Memory Reference Table
20 milestone upper limits from 10 to 1 billion. Click "Inspect" to see how few primes need to be tested:
| Limit (N) | Cutoff ⌊√N⌋ | Primes to Check | Primes Found π(N) | Memory Needed | Notes | Action |
|---|---|---|---|---|---|---|
| 10 | 3 | 2 | 4 | 1.25 B | Primes 2, 3, 5, 7 | |
| 25 | 5 | 3 | 9 | 3.12 B | Primes 2, 3, 5 sieved | |
| 50 | 7 | 4 | 15 | 6.25 B | Primes up to 7 | |
| 100 | 10 | 4 | 25 | 12.5 B | Standard 100-grid; 25 primes | |
| 200 | 14 | 6 | 46 | 25 B | Sieves up to prime 13 | |
| 500 | 22 | 8 | 95 | 62.5 B | Sieves up to prime 19 | |
| 1,000 | 31 | 11 | 168 | 125 B | Millennium milestone π(1000) = 168 | |
| 2,000 | 44 | 14 | 303 | 250 B | Sieves up to prime 43 | |
| 5,000 | 70 | 19 | 669 | 625 B | Sieves up to prime 67 | |
| 10,000 | 100 | 25 | 1,229 | 1.22 KB | Fits inside L1 data cache | |
| 50,000 | 223 | 47 | 5,133 | 6.1 KB | Sieves only 47 primes | |
| 100,000 | 316 | 65 | 9,592 | 12.2 KB | 65 primes find 9,592 primes | |
| 500,000 | 707 | 125 | 41,538 | 61 KB | Sieves 125 primes | |
| 1,000,000 | 1,000 | 168 | 78,498 | 122 KB | One million primes; 168 base primes | |
| 5,000,000 | 2,236 | 333 | 348,513 | 610 KB | Sieves 333 primes | |
| 10,000,000 | 3,162 | 446 | 664,579 | 1.19 MB | Ten million mark | |
| 50,000,000 | 7,071 | 908 | 3,001,134 | 5.96 MB | Sieves 908 primes | |
| 100,000,000 | 10,000 | 1229 | 5,761,455 | 11.9 MB | 10⁸ mark; 5.76 million primes | |
| 500,000,000 | 22,360 | 2506 | 26,355,867 | 59.6 MB | Sieves 2,506 primes | |
| 1,000,000,000 | 31,622 | 3401 | 50,847,534 | 119 MB | One billion: 3,401 base primes |
Segmented Sieve & Fast Processor Cache
The standard sieve creates one large list in memory. When N reaches tens of millions, this list becomes too big to fit inside your computer's high-speed CPU cache, forcing it to fetch data from slower RAM memory. A Segmented Sieve fixes this by dividing the large list into small blocks that fit right inside the CPU cache:
05. Step-by-Step Worked Examples
Start at 2² = 4. Count by 2s to cross out all 49 even composite numbers (4, 6, 8, ..., 100). Half the numbers in the grid are eliminated in one pass!
Start at 3² = 9 (skipping 6, which was already crossed out by 2). Cross out remaining multiples of 3: 9, 15, 21, ..., 99. Eliminates 16 newly seen composite numbers.
Start at 5² = 25 (skipping 10, 15, 20). Only composite numbers ending in 5 that are not multiples of 2 or 3 remain: 25, 35, 55, 65, 85, 95. Eliminates 6 new numbers.
Start at 7² = 49 (skipping 14, 21, 28, 35, 42). Only 2 composite numbers remain: 49 and 7 × 13 = 91. Because the square root of 100 is 10, all 25 primes up to 100 are now proven!
06. Prime Sieve Methods Compared
| Sieve Method | Speed (Time Steps) | Memory Used | How It Works | Real-World Performance |
|---|---|---|---|---|
| Standard Eratosthenes | O(N log log N) | Small (1 bit per number) | Crosses out multiples step by step | Very fast up to 10 million; slows when memory gets large |
| Segmented Sieve | O(N log log N) | Tiny (fits in CPU cache) | Processes numbers in small blocks | World-record speeds up to 1 trillion |
| Wheel Factorization | O(N log log N) | 73% less memory | Skips multiples of 2, 3, and 5 automatically | Skips over 70% of candidate numbers upfront |
| Sieve of Atkin | O(N / log log N) | Small | Uses quadratic equations | Theoretically fewer steps; higher code complexity |
Related Prime & Sieve Tools
Frequently Asked Questions
What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is a clever ancient method invented over 2,200 years ago by Greek mathematician Eratosthenes. It finds every prime number up to a limit by listing all numbers in a grid and crossing out multiples (like 4, 6, 8, 9, 10...) until only prime numbers remain.
Why does the sieve start crossing out multiples at p²?
Because any smaller multiple has already been crossed out by a smaller prime! For example, when checking prime 5, its smaller multiples (2×5=10, 3×5=15, 4×5=20) were already crossed out when checking 2 and 3. So the very first number 5 needs to cross out is 5 × 5 = 25.
Why does the algorithm stop at √N?
If a number is composite, it must have at least one factor that is smaller than or equal to its square root. For example, for numbers up to 100, the square root is 10. Once you cross out multiples of 2, 3, 5, and 7 (all primes under 10), every composite number up to 100 has already been crossed out! Any number left unmarked is guaranteed to be prime.
How fast and memory-efficient is the Sieve of Eratosthenes?
It is remarkably fast. It takes O(N log log N) steps, which means finding primes up to 1,000,000 takes only about 3 million quick operations—much faster than testing each number one by one. In computer memory, each number only needs a single true/false bit, taking less than 125 kilobytes for 1 million numbers.
What is a Segmented Sieve and why is it used?
When you want to find primes up to huge limits (like 1 billion), storing the whole grid at once takes too much memory and slows down your computer's processor. A Segmented Sieve solves this by slicing the giant list into small chunks (or segments) that easily fit in your computer's fastest processor cache.
How does the Sieve of Eratosthenes compare to the Sieve of Atkin?
The Sieve of Atkin is a modern method invented in 2003 that uses quadratic equations to skip even more numbers. In theory it uses fewer steps, but because the math is more complicated, a well-optimized Sieve of Eratosthenes is usually faster and simpler in real software.
What is wheel factorization and how does it help?
Wheel factorization is a trick that skips obvious multiples (like all multiples of 2, 3, and 5) before you even start crossing things out. By skipping even numbers and multiples of 3 and 5 right away, you eliminate over 70% of the numbers before doing any work!