- Foundation
- About 15 min
- 5 practice questions
Prime and composite numbers and the Sieve of Eratosthenes
Tell prime numbers from composite numbers using factors and rectangle arrangements, list the primes up to 100 with the Sieve of Eratosthenes, and reason about twin primes.
If something looks wrong, please tell us.
By the end of this lesson you can
- Define prime and composite numbers and explain why 1 is neither.
- Use the Sieve of Eratosthenes to list the primes up to 100, and explain why it works.
- Answer true-or-false questions about primes with reasons.
Some numbers can be split into equal rows in many ways; others refuse to be split at all. These stubborn numbers, the primes, are the building blocks of every whole number, and mathematicians have studied them for thousands of years.
Rectangles of counters
Arrange 12 counters in a rectangle: 1 × 12, 2 × 6, 3 × 4 (and the same turned round). The rows and columns are always factors of 12. Now try 13 counters: the only rectangle is 1 × 13, a single line. 13 has only two factors, 1 and 13.
Whole numbers from 1 upwards
-
1
- Only one factor
- Neither prime nor composite
-
Prime numbers
- Exactly two factors: 1 and itself
- 2, 3, 5, 7, 11, 13, 17, 19, …
-
Composite numbers
- More than two factors
- 4, 6, 8, 9, 10, 12, 14, 15, …
A prime number has exactly two factors: 1 and itself. A composite number has more than two factors. 1 has only one factor, so it is neither prime nor composite. 2 is the only even prime: every other even number has 2 as a factor as well as 1 and itself.
The Sieve of Eratosthenes
Eratosthenes, a Greek mathematician of about 2,200 years ago, found a neat way to list primes. Write the numbers 1 to 100 in a grid of ten columns, then sieve them:
Sieving out the primes up to 100
- Cross out 1 It is neither prime nor composite.
- Circle 2 Cross out every later multiple of 2: 4, 6, 8, …
- Circle 3 The next number not crossed out; cross out its later multiples: 6, 9, 12, …
- Circle 5, then 7 Cross out their later multiples.
- Circle the rest Every number left uncrossed is prime.
Why does it work? A number is crossed out only if it is a multiple of a smaller prime, so it has a factor other than 1 and itself: it is composite. A number that survives has no smaller prime factor, so it is prime. For numbers up to 100, sieving with 2, 3, 5 and 7 is enough, because the next prime, 11, has 11 × 11 = 121, which is already more than 100: any composite number up to 100 has a prime factor of 7 or less.
| Numbers | Primes | How many |
|---|---|---|
| 1–10 | 2, 3, 5, 7 | 4 |
| 11–20 | 11, 13, 17, 19 | 4 |
| 21–30 | 23, 29 | 2 |
| 31–40 | 31, 37 | 2 |
| 41–50 | 41, 43, 47 | 3 |
| 51–60 | 53, 59 | 2 |
| 61–70 | 61, 67 | 2 |
| 71–80 | 71, 73, 79 | 3 |
| 81–90 | 83, 89 | 2 |
| 91–100 | 97 | 1 |
Worked example 1: is it prime?
(a) 51: 5 + 1 = 6 suggests trying 3; 51 = 3 × 17, so 51 is composite. (b) 37: not divisible by 2, 3 or 5, and 7 × 5 = 35, 7 × 6 = 42, so not by 7. Since 7 × 7 = 49 > 37, no larger factor needs checking. 37 is prime. (c) 91: 91 = 7 × 13, so it is composite, even though it looks prime.
Worked example 2: twin primes and gaps
Twin primes are primes that differ by 2. Below 100 they are 3 and 5, 5 and 7, 11 and 13, 17 and 19, 29 and 31, 41 and 43, 59 and 61, 71 and 73: 8 pairs. Gaps can also be long: 90, 91, 92, 93, 94, 95 and 96 are seven composite numbers in a row, since 89 and 97 are the primes on either side.
Worked example 3: true or false?
- 'No prime ends in 4.' True: a number ending in 4 is even and bigger than 2, so 2 is a factor.
- 'Prime numbers have no factors.' False: every prime has exactly two factors, 1 and itself.
- 'All even numbers are composite.' False: 2 is even and prime.
- 'A product of two primes can be prime.' False: 3 × 5 = 15 has the factors 3 and 5 as well as 1 and 15.
A prime has exactly two factors, 1 and itself. A composite number has more than two. 1 is neither, and 2 is the only even prime.
Key takeaways: count the factors to classify a number. The Sieve of Eratosthenes crosses out multiples of each prime in turn; what survives is prime. There are 25 primes up to 100, and to test a number up to 100 you only need to try dividing by 2, 3, 5 and 7.
Check your understanding
-
1. Which of these numbers is prime?
- 51
- 57
- 87
- 53
Show answer
Answer: D. 53 is not divisible by 2, 3, 5 or 7 (7 × 7 = 49 and 7 × 8 = 56), so it is prime. 51 = 3 × 17, 57 = 3 × 19 and 87 = 3 × 29 are composite.
-
2. Why is 1 neither prime nor composite?
- Because it is odd
- Because it has only one factor
- Because it has no factors
- Because it is the smallest number
Show answer
Answer: B. A prime needs exactly two factors and a composite needs more than two. 1 has only one factor (itself), so it is neither.
-
3. How many prime numbers are there between 20 and 30?
- 1
- 3
- 2
- 4
Show answer
Answer: C. Check 21 to 29: 21 = 3 × 7, 22 even, 23 prime, 24 even, 25 = 5 × 5, 26 even, 27 = 3 × 9, 28 even, 29 prime. So there are 2 primes: 23 and 29.
-
4. In the Sieve of Eratosthenes for 1 to 100, after crossing out multiples of 2, 3, 5 and 7, why can we stop?
- Because 11 × 11 = 121 is more than 100
- Because there are no primes after 7
- Because 100 is even
- Because 7 is the largest prime
Show answer
Answer: A. Any composite number up to 100 must have a prime factor no bigger than 10; the next prime 11 would need a partner of at least 11, and 11 × 11 = 121 > 100.
-
5. Which pair are twin primes?
- 23 and 25
- 31 and 33
- 41 and 43
- 51 and 53
Show answer
Answer: C. Twin primes are two primes that differ by 2. 41 and 43 are both prime. 25 = 5 × 5, 33 = 3 × 11 and 51 = 3 × 17 are composite.
Sign in to keep track of the lessons you finish.