The Sieve of Eratosthenes is a classic method for finding all prime numbers up to a chosen limit. It matters because prime numbers are the building blocks of whole-number multiplication, and many math topics depend on recognizing them quickly. Instead of testing every number one by one, the sieve removes numbers that are known to be composite.
This makes it an efficient and visual way to see the structure of the integers.
Key Facts
- A prime number has exactly two positive factors: 1 and itself.
- A composite number has more than two positive factors.
- Start the sieve by listing the integers from 2 to n, since 1 is not prime.
- When a prime p is found, cross out its multiples: 2p, 3p, 4p, and so on.
- You only need to test primes p with p <= sqrt(n).
- For n = 100, checking primes up to sqrt(100) = 10 means using 2, 3, 5, and 7.
Vocabulary
- Prime number
- A prime number is a whole number greater than 1 with exactly two positive factors, 1 and itself.
- Composite number
- A composite number is a whole number greater than 1 that has more than two positive factors.
- Multiple
- A multiple of a number is the result of multiplying that number by an integer.
- Factor
- A factor of a number is a whole number that divides it evenly with no remainder.
- Square root
- The square root of n is a number that gives n when multiplied by itself.
Common Mistakes to Avoid
- Treating 1 as prime is wrong because 1 has only one positive factor, not exactly two.
- Crossing out the prime number itself is wrong because the sieve removes multiples of a prime after the prime, such as 2p, 3p, and 4p.
- Checking every number up to n is unnecessary because any composite number up to n must have at least one factor less than or equal to sqrt(n).
- Starting each crossing-out step at 2p instead of p^2 wastes work because smaller multiples of p were already crossed out by smaller prime factors.
Practice Questions
- 1 Use the Sieve of Eratosthenes to list all prime numbers from 1 to 50.
- 2 Using the sieve up to 100, which numbers are crossed out when you use the prime 7 and start at 7^2?
- 3 Explain why, when sieving up to 100, it is enough to cross out multiples of 2, 3, 5, and 7.