The Sieve of Eratosthenes - Sixth Grade Mathematics
The Sieve of Eratosthenes is an ancient, elegant algorithm developed by the Greek mathematician Eratosthenes of Cyrene over 2,200 years ago to systematically identify all prime numbers within any given range.
The Mechanical Principle of the Sieve
Imagine pouring a mixture of sand and small pebbles through a mesh wire screen. The fine sand grains slip through the holes, while the larger pebbles remain trapped on top. The Sieve of Eratosthenes acts as a mathematical filter: by systematically crossing out all composite multiples of known primes, only the prime numbers remain untouched.
+-------------------------------------------------------------------------+
| THE SIEVE OF ERATOSTHENES PROTOCOL |
| |
| Step 1: Write down all integers from 1 to 100 in a 10x10 grid. |
| Step 2: Cross out 1 (1 is neither prime nor composite). |
| Step 3: Circle 2 (the first prime). Cross out all multiples of 2. |
| Step 4: Circle 3 (next prime). Cross out all remaining multiples of 3.|
| Step 5: Circle 5 (next prime). Cross out all remaining multiples of 5.|
| Step 6: Circle 7 (next prime). Cross out all remaining multiples of 7.|
| Step 7: All remaining uncrossed numbers up to 100 are PRIMES! |
+-------------------------------------------------------------------------+
The Square Root Stopping Boundary
Why does the algorithm stop crossing out multiples after testing the prime 7 for a 1-to-100 grid? Consider any composite number n up to 100. If n = a * b, both a and b cannot be strictly greater than the square root of 100 (which is 10). At least one factor must be less than or equal to 10. The prime numbers less than 10 are 2, 3, 5, and 7. Therefore, once all multiples of 2, 3, 5, and 7 have been eliminated, any composite number less than or equal to 100 has already had at least one of its factors crossed out. All remaining numbers must be prime.
Visualizing the 1-to-100 Sieve Results
Applying the sieve to the integers 1 through 100 reveals exactly 25 prime numbers.
+-------------------------------------------------------------------------+
| THE 25 PRIMES UNDER 100 IDENTIFIED |
| |
| 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, |
| 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, |
| 73, 79, 83, 89, 97 |
+-------------------------------------------------------------------------+
Step-by-Step Elimination Observations
When crossing out multiples of 2, half of the numbers on the grid disappear immediately (all numbers ending in 0, 2, 4, 6, 8, except 2 itself). When crossing out multiples of 3, numbers like 6, 12, 18 were already crossed out by 2; the first new composite eliminated by 3 is 3^2 = 9. When testing 5, the first new composite eliminated is 5^2 = 25 (since 10, 15, and 20 were already crossed out by 2 and 3). For 7, the first new composite eliminated is 7^2 = 49 (since 14, 21, 28, 35, and 42 were already crossed out). The next prime is 11, and its first uncrossed multiple would be 11^2 = 121, which exceeds 100.
Patterns in Prime Distribution
Examining the 25 prime numbers between 1 and 100 reveals several patterns.
Decade Breakdown of Primes:
1 to 10: [ 2, 3, 5, 7 ] --> 4 primes
11 to 20: [ 11, 13, 17, 19 ] --> 4 primes
21 to 30: [ 23, 29 ] --> 2 primes
31 to 40: [ 31, 37 ] --> 2 primes
41 to 50: [ 41, 43, 47 ] --> 3 primes
51 to 60: [ 53, 59 ] --> 2 primes
61 to 70: [ 61, 67 ] --> 2 primes
71 to 80: [ 71, 73, 79 ] --> 3 primes
81 to 90: [ 83, 89 ] --> 2 primes
91 to 100: [ 97 ] --> 1 prime (91 = 7*13)
Prime Density and the Infinitude of Primes
Notice that primes become somewhat sparser as numbers grow larger. Between 1 and 20 there are 8 primes (40 percent), whereas between 81 and 100 there are only 3 primes (15 percent). Despite this thinning, prime numbers never stop. Around 300 BCE, the mathematician Euclid proved that there are infinitely many prime numbers, meaning no matter how far you count, you will always encounter more primes.
Exercises
Exercise 1. If you wanted to use the Sieve of Eratosthenes to find all prime numbers up to 200, what is the largest prime whose multiples you would need to cross out?
Exercise 2. What is the very first composite number crossed out by the prime number 11 that was not already eliminated by 2, 3, 5, or 7?
Exercise 3. Explain why 91 is frequently mistaken for a prime number, and show how the Sieve of Eratosthenes identifies it as composite.
Solutions
Solution to Exercise 1. To determine the stopping boundary for numbers up to 200, find the square root of 200. Since 14^2 = 196 and 15^2 = 225, the square root of 200 is approximately 14.14. The prime numbers less than or equal to 14 are 2, 3, 5, 7, 11, and 13. Therefore, 13 is the largest prime whose multiples must be crossed out.
Solution to Exercise 2. Multiples of 11 with smaller factors (such as 11 * 2 = 22, 11 * 3 = 33, 11 * 5 = 55, and 11 * 7 = 77) are already eliminated during the passes for 2, 3, 5, and 7. The first multiple of 11 that has no factor smaller than 11 is 11 * 11 = 11^2 = 121.
Solution to Exercise 3. The number 91 is often mistaken for a prime number because it is an odd number that does not end in 5 and its digits sum to 9 + 1 = 10 (not divisible by 3). Furthermore, it is not divisible by 2. However, during the Sieve of Eratosthenes step where multiples of 7 are crossed out, dividing 91 by 7 gives exactly 13 with zero remainder (7 * 13 = 91). Because it has four factors (1, 7, 13, 91), it is composite.