Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools


Sieve of Eratosthenes


Press Start to begin the sieve
÷2
÷3
÷5
÷7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
0
Primes
0
Composites
2
Current
Step-by-Step
Press Start to begin. Each prime divisor will appear here with its crossed-out multiples.

How to Use the Sieve Visualization
Understanding the Grid Display
Reading the Status Bar
Using the Step-by-Step Panel
Tracking Statistics
What is the Sieve of Eratosthenes?
Why Start at p²?
Prime Numbers and Their Properties
Algorithm Complexity and Efficiency
Patterns in Prime Distribution
Related Concepts




How to Use the Sieve Visualization

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.

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.

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.

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.

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(nlog⁡log⁡n)O(n \log \log n), where n is the upper limit. This is nearly linear and much faster than testing each number individually with trial division, which takes O(nn)O(n \sqrt{n}).

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 only by its smallest prime factor, minimizing redundant work.

Space complexity is O(n)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)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.