Sieve of Eratosthenes
Step through composite-marking passes and identify all primes up to a chosen bound.
By Riano · Published · Updated · Report a correction
Sieve of Eratosthenes
Finding primes bounded by N
The Sieve of Eratosthenes is an ancient and highly efficient algorithm for finding all prime numbers up to a given limit N. It works iteratively by marking the multiples of each prime, starting with 2. By only processing primes p where p2 ≤ N and marking their multiples starting from p2, the algorithm minimizes redundant work.
How it works
We start with a list of numbers from 2 up to the limit N (0 and 1 are never prime). We find the first unmarked number, which is a prime, and mark all its multiples as composite (not prime). We repeat this for each subsequent unmarked number. A key optimization is that we only need to test up to the square root of N. Any composite number less than N must have a prime factor less than or equal to the square root of N.
Worked Example: N = 30
Let's trace the algorithm to find all primes up to 30. We list the numbers from 2 to 30 and begin finding primes.
| Prime p | Start p2 | Marked Composites |
|---|---|---|
| 2 | 4 | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 |
| 3 | 9 | 9, 15, 21, 27 (12, 18, 24, 30 already marked) |
| 5 | 25 | 25 |
The next unmarked prime is 7. Since 72 = 49 > 30, the algorithm terminates. The remaining unmarked numbers are the primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. A total of 10 primes are found.
Experiment in the Module
Open the Sieve of Eratosthenes explorer to step through the marking process visually.
- Set Limit N to 49 and click Reset to begin at the initial state.
- Click Step to process p = 2. You will see 4, 6, 8, ... up to 48 marked as composites.
- Click Step to process p = 3, marking its multiples starting from 9.
- Click Step to process p = 5, marking its multiples starting from 25.
- Click Step to process p = 7, marking its multiple 49 (which is exactly 72).
- The fourth pass completes the trace: the next unmarked prime is 11, and 112 > 49. Step is now disabled, and the 15 primes up to 49 are visible.
- Click Reset to rewind the same Limit N, then Finish to reveal all four passes instantly.
Limitations
This explorer is intentionally bounded to N ≤ 80 for instructional visualization in a responsive grid. In practice, the Sieve of Eratosthenes has a time complexity of O(N log(log N)) and requires O(N) memory for the standard marking array. This bounded replay additionally stores a marking set for every pass, so its saved trace uses more storage than that single-array implementation. For massive limits (like generating billions of primes), memory limits become an issue, requiring advanced techniques like the Segmented Sieve. Additionally, while the sieve constructs lists of primes efficiently, it is not used directly for testing the primality of a single, massive 2048-bit number in systems like RSA.
References
The mathematical principles underlying this visual explorer are based on classical number theory. You can find more formal definitions and computational bounds below.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Sieve of Eratosthenes module.
Try Sieve of Eratosthenes on Riano →