Press Start to begin. Each prime divisor will appear here with its crossed-out multiples.
The grid is uncommitted: every number from 2 to 100 is still a candidate. The algorithm will decide by elimination, never by division. Learn more about the controls · The algorithm
This interactive tool demonstrates the Sieve of Eratosthenes algorithm on numbers from 1 to 100. Press the Start button to run the animation automatically, watching as primes emerge and composites get crossed out.
Use the Step button to advance one action at a time for closer study. Each step either identifies a new prime or crosses out one of its multiples. The Reset button clears the grid and returns to the initial state.
The Speed slider controls how fast the animation runs. Slide left for slower, more detailed observation; slide right for faster execution. Even at maximum speed, each crossing is visible so you can follow the pattern.
Initial grid, frozen
One hundred neutral cells; only 1 is grayed out from the start — neither prime nor composite, it takes no part in the sieve.
The frozen frame above is the tool at rest: one hundred cells, none yet judged. Only 1 is grayed out from the start—it is neither prime nor composite, so the algorithm never touches it. Everything else is, for the moment, a candidate.
That neutrality is the honest starting point of the sieve: it assumes nothing and eliminates rather than tests. What each color will come to mean once the run begins is covered under the grid display.
Understanding the Grid Display
The main grid shows numbers 1 through 100 arranged in 10 rows of 10. Number 1 appears gray because it is neither prime nor composite — by definition, primes must have exactly two distinct divisors.
As the algorithm runs, primes light up in solid colors: blue for 2, green for 3, purple for 5, and orange for 7. These are the only primes whose multiples need crossing within 100, since the next prime (11) has 11² = 121 > 100.
Composite numbers show tinted backgrounds indicating which prime(s) crossed them out. Numbers divisible by multiple small primes display striped patterns combining those colors. This color coding reveals divisibility relationships at a glance.
Sieve complete, frozen
The verdict: 25 solid primes and 74 tinted composites. Each tint records the small primes that divide that cell.
The finished grid above is the whole story in one frame: 25 solid primes, 74 tinted composites, and gray 1. Read any composite's tint as a partial factorization—66 wears the stripes of 2 and 3, 70 of 2, 5, and 7. Only factors up to 7 are recorded; 94 = 2 × 47 shows pure blue because 47 lies beyond the sieve's palette.
The finished frame also displays the thinning documented under patterns in prime distribution: solid cells crowd the early rows and scatter toward the bottom.
Reading the Status Bar
The status bar between the controls and grid displays the current action. Before starting, it shows "Press Start to begin the sieve." During execution, it narrates each step.
When a prime is found, the status reads "Found prime X — crossing out multiples." When crossing a specific multiple, it shows "Crossing out Y (X × Z)" where Y is the composite being marked and Z is the multiplier.
Upon completion, the status announces "Complete! Found all primes up to 100." The legend on the right side of the status bar shows the color key for divisibility by 2, 3, 5, and 7.
Using the Step-by-Step Panel
The right panel provides detailed explanations organized by divisor. Each prime that processes multiples gets its own card showing which numbers it crossed out.
The card header shows the divisor (÷2, ÷3, etc.) and explains the starting point: "Cross out multiples of p starting from p² = ..." This explains why the sieve skips smaller multiples — they were already handled by smaller primes.
Below the header, crossed numbers appear as colored badges. The count at the bottom tracks how many composites this divisor eliminated. Active cards highlight while that prime's multiples are being processed.
Tracking Statistics
Three statistics cards at the top of the right panel show running totals. Primes counts how many prime numbers have been confirmed. Composites counts how many numbers have been crossed out. Current displays the prime currently being processed.
Watch these numbers change as the algorithm progresses. By completion, you'll see 25 primes and 74 composites (plus 1, which is neither). The Current indicator shows "—" when the sieve finishes.
These real-time statistics help you understand the density of primes. Notice that most crossings happen early (multiples of 2 eliminate half the grid), while later primes find fewer uncrossed multiples.
What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is an ancient algorithm attributed to the Greek mathematician Eratosthenes of Cyrene (c. 276–194 BCE). It finds all prime numbers up to any given limit through systematic elimination of composites.
The algorithm works by iterating through numbers starting at 2. For each unmarked number p, it marks p as prime, then crosses out all multiples of p (starting from p²). The process continues until reaching √n, since any composite larger than √n must have a factor smaller than √n.
Unlike trial division, which tests each candidate individually, the sieve processes numbers in bulk. This makes it remarkably efficient — finding primes up to one million takes mere milliseconds on modern computers.
The sieve's opening move is its largest. The first unmarked number is 2, so 2 is prime — and its multiples fall in a single sweep: 4, 6, 8, and every even number up to 100. Forty-nine composites are eliminated at once, half the grid.
Because the grid is 10 columns wide and 2 divides 10, the crossed cells line up in five clean vertical stripes — the even columns. No later pass will look this orderly.
The status bar narrates each crossing as "Crossing out Y (2 × Z)", and the ÷2 card in the step-by-step panel collects all forty-nine. When the sweep ends, the first survivor is 3 — the next prime, already guaranteed.
After the ÷2 sweep, frozen
Blue 2 and forty-nine blue-tinted multiples in five even columns: one pass, half the grid settled. The first survivor, 3, is next.
The sweep starts at 4, which is just the p² rule in its degenerate case: below 2² there are no composite multiples to cross. From here on, every remaining candidate is odd.
Half the work of the entire sieve happens in this one pass — a preview of the efficiency argument made under algorithm complexity: each prime p crosses about n/p numbers, so small primes do almost everything and later primes arrive to find their work mostly done.
The Second Pass: Multiples of 3
After 2's sweep, the smallest survivor is 3 — prime by survival. Its multiples fall from 9 onward: 9, 12, 15, 18, and so on in steps of three.
This is the pass where the grid's most distinctive feature first appears: stripes. Every second multiple of 3 is even and already blue, so numbers like 12, 18, and 24 now carry both colors in a striped pattern — a visible record that two primes divide them. The genuinely new crossings are the odd multiples: 9, 15, 21, 27, and their kin, sixteen numbers in all.
In the 10-column layout the multiples of 3 run diagonally, since three steps move one column left and never repeat a column within a row cycle.
After the ÷3 sweep, frozen
Green 3 and its multiples from 9 up. Numbers divisible by both 2 and 3 — 12, 18, 24 and their kin — now wear both colors striped.
After this pass, the survivors thin dramatically: any number still unmarked is divisible by neither 2 nor 3, which forces it into the residues 6k±1 — the pattern noted under prime distribution. Two passes have already confined all future primes to a third of the number line.
The stripes are worth a second look: they are the beginning of a prime factorization drawn in color. A cell's pattern lists the small primes that divide it, in the order the sieve found them.
Why Start at p²?
A key optimization in the sieve is starting each prime's elimination at p² rather than 2p. This works because every multiple of p smaller than p² has already been eliminated by a smaller prime.
Consider p = 5. The multiples 10, 15, and 20 equal 2×5, 3×5, and 4×5 respectively. Since 2 < 5 and 3 < 5 and 4 = 2×2, these were crossed out when processing 2 or 3. The first "new" multiple is 5×5 = 25.
This optimization explains why only primes up to √n need processing. For n = 100, we check primes up to 10, meaning 2, 3, 5, and 7. The next prime, 11, has 11² = 121 > 100, so all remaining unmarked numbers are already confirmed prime.
After the ÷5 sweep, frozen
Purple 5 crosses only six new numbers — 25, 35, 55, 65, 85, 95. Everything smaller was already gone before the sweep began.
The frozen frame above catches the sieve just after 5's sweep, and the p² rule is visible in the counts: of the sixteen multiples of 5 in range, only six — 25, 35, 55, 65, 85, 95 — are newly crossed in purple. The other ten already carried blue or green from earlier passes; 5 merely adds its stripe to their pattern.
Notice what the six newcomers have in common: each is 5 times a number whose smallest prime factor is 5 or more (25 = 5×5, 35 = 5×7, 55 = 5×11 …). That is the p² principle stated backwards—a multiple of 5 escapes the earlier sweeps only if its other factor has no small primes in it. The final pass for 7 pushes the same logic to its endpoint.
The Last Pass: Multiples of 7
By the time 7 is declared prime, the grid is nearly settled. Its sweep starts at 7² = 49 and touches 49, 56, 63, 70, 77, 84, 91, and 98 — but only three of them are new: 49, 77, and 91. The other five already carried colors from 2, 3, or 5.
The number 91 deserves its moment. It looks prime — odd, digit sum 10, ends in 1 — yet 91 = 7 × 13, and this sweep is the only one that catches it. It is the classic trap for anyone testing primality by instinct.
After 7, the next unmarked number is 11, and 11² = 121 lies beyond the grid. The sieve then does something satisfying: it promotes every remaining unmarked number to prime simultaneously — twenty-one numbers confirmed in a single step.
After the ÷7 sweep, frozen
Orange 7 catches just three newcomers: 49, 77, and 91. With 11² beyond the grid, every survivor is now provably prime.
The mass promotion is the √n stopping rule in action: a composite number must have a factor no larger than its square root, so any composite up to 100 would have been caught by 2, 3, 5, or 7. Survival past four sweeps is a proof of primality, not an absence of evidence.
Fittingly, the last pass is also the smallest — three new crossings against the first pass's forty-nine. The sieve's work shrinks geometrically, which is what the O(nloglogn) bound under algorithm complexity measures precisely.
Prime Numbers and Their Properties
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.
The number 2 is special — it's the only even prime. Every other even number is divisible by 2 and therefore composite. This is why the sieve eliminates half the grid in its first pass.
The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be uniquely expressed as a product of primes. This makes primes the "building blocks" of all numbers, giving them central importance in number theory and applications like cryptography.
Algorithm Complexity and Efficiency
The Sieve of Eratosthenes has time complexity O(nloglogn), where n is the upper limit. The O(⋅) is big-O notation: it names how the work grows as n grows, ignoring constant factors and slower-growing terms, so it compares methods rather than predicting a running time. This is nearly linear and much faster than testing each number individually with trial division, which takes O(nn).
The efficiency comes from avoiding division entirely. Instead of asking "is this number prime?", the sieve marks multiples using simple addition. Each composite gets marked first by its smallest prime factor, minimizing redundant work.
Space complexity is O(n) for storing the array of marks. Optimizations exist: storing only odd numbers halves memory usage, and segmented sieves process ranges in chunks to handle very large limits.
Patterns in Prime Distribution
Watch the grid as primes emerge and notice patterns. Primes become less frequent as numbers grow — there are 10 primes between 1-25 but only 6 between 76-100. This reflects the Prime Number Theorem: primes near n have density approximately 1/ln(n).
Observe that after 2, all primes are odd. After 3, all primes avoid multiples of both 2 and 3, appearing only at positions 6k±1. These patterns inspire more advanced sieves that skip known non-primes.
Twin primes — pairs differing by 2 like (11,13) and (17,19) — appear scattered through the grid. The Twin Prime Conjecture suggests infinitely many exist, though this remains unproven.
Related Concepts
The Sieve of Eratosthenes connects to many topics in number theory and computer science:
Prime Factorization: Every composite crossed by the sieve has a smallest prime factor. Collecting these factors decomposes any number into primes.
Divisibility: The sieve visually demonstrates divisibility — colored stripes show which small primes divide each composite.
GCD and LCM: Finding greatest common divisors and least common multiples relies on prime factorizations that the sieve helps identify.
Cryptography: Large primes are essential for RSA encryption. While the basic sieve handles small ranges, related algorithms generate the massive primes used in security.
Computational Number Theory: Modern variants like the Sieve of Atkin and segmented sieves extend these ideas to find primes among billions.