Before this page: be able to list the factors of a number in pairs and know where the trials stop, read the tests for 2, 3 and 5 from multiples and divisibility tests, and divide with short division.
Numbers that make one rectangle
12 counters make three rectangles: 1 × 12, 2 × 6 and 3 × 4. The length of each side is a factor of 12, so 12 has six factors: 1, 2, 3, 4, 6 and 12.
13 counters make one.
Rows from 13 counters
13 counters in a row
1 × 13: one row of 13, the widest rectangle there is.
A prime has exactly two factors: 1 and itself
Why 1 is out and 2 is in
A single counter is the rectangle 1 × 1, and both sides are 1, so 1 has one factor; a prime needs two, so 1 is not prime.
2 has exactly two, 1 and 2, so 2 is prime. Every larger even number has 2 as a third factor beside 1 and itself, so 2 is the only even prime.
Crossing out multiples leaves the primes
Fifty numbers tested one at a time is fifty factor lists. Crossing out multiples finds the same primes with no lists at all: every multiple of 2 beyond 2 itself has 2 as a third factor, and the same goes for 3, 5 and 7.
Cross out the multiples from 1 to 50
The numbers 1 to 50
1 is set aside, and the crossing starts at 2.
Each of 2, 3, 5 and 7 makes its first new cross at its own square: every smaller multiple of 5 is 5 × 2, 5 × 3 or 5 × 4, and the smaller factor crossed it first.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
- Every number from 2 to 50 not on the list is a multiple of 2, 3, 5 or 7.
- The list runs on to 100 with 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97: twenty-five primes in all, sieved by the same four.
Try the primes in turn, and stop once a square passes the number
97 is tested on its own, with no sieve:
Try the primes 2, 3, 5, 7, 11, … as candidate factors in turn, and stop once a candidate's square is past the number under test
- An exact division finds a factor pair, so the number under test is not prime and the trials stop there.
- A remainder from every candidate factor before the stop means the number under test is prime.
- Only primes are candidates: every 4 is two 2s, so anything 4 divides, 2 divides already, and 6, 8 and 9 divide only what 2 or 3 divides.
Why a candidate's square is where the trials stop
In any factor pair, the smaller factor multiplied by itself is at most the number under test. For 97, 11 × 11 = 121 is past 97, so the smaller factor of any pair for 97 is below 11.
Every number from 2 to 10 is a multiple of 2, 3, 5 or 7. Once those four candidates leave remainders, no number from 2 to 10 divides 97, and 97 has no pair but 1 × 97.
Test 97
97 on the line
Counting in 2s, 3s, 5s and 7s from zero: a count that lands on 97 is an exact division, and one that falls short leaves its gap as the remainder.
91 is not prime, and none of the tests for 2, 3 and 5 says so.
Test 91
91 on the line
91 is odd, its digits add to 10 and it ends in 1, so the digit tests rule out the candidates 2, 3 and 5 before any count begins.
An exact division ends the test
Example: test 117
Try the candidate factors in turn, and stop at the first exact division.
- 117 ÷ 2 = 58 r 1 117 ends in 7, so it is odd and the candidate 2 leaves a remainder.
- 1 + 1 + 7 = 9 The digits add to a multiple of 3, so the candidate 3 divides 117 exactly.
- 117 = 3 × 39 3 and 39 are a factor pair of 117, so 117 is not prime, and no further candidate needs trying.
Three-digit numbers need no candidate past 31
Any whole number up to 999 needs only the candidate factors 2 to 31: 31 × 31 = 961 is under 999 and 37 × 37 = 1,369 is past it.
- 2211 ÷ 2 = 105 r 1
- 3211 ÷ 3 = 70 r 1
- 5211 ÷ 5 = 42 r 1
- 7211 ÷ 7 = 30 r 1
- 11211 ÷ 11 = 19 r 2
- 13211 ÷ 13 = 16 r 3
- 1717 × 17 = 289 is past 211
- 19
- 23
- 29
- 31
- 37
211 is prime: the candidates 2, 3, 5, 7, 11 and 13 each leave a remainder, and 17 × 17 = 289 is past 211.
A whole number from 1 to 999 is needed.
Common mistakes
- Calling 51 prime because it is odd Odd rules out the candidate 2 and nothing else. 51 = 3 × 17 and 57 = 3 × 19: the digit sums 6 and 12 are multiples of 3.
- Stopping before the square For 49, 7 × 7 = 49 is not past 49, so the candidate 7 is still tried, and it divides: 49 = 7 × 7. Trying only 2, 3 and 5 calls 49 prime.
Summary
- A prime has exactly two factors, 1 and itself: 13 is prime, and 12, with six factors, is not.
- 1 has one factor, so it is not prime; 2 has two, so it is, and it is the only even prime.
- The fifteen primes up to 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
- To test a number, try the primes 2, 3, 5, 7, 11 and on as candidate factors, and stop once a candidate's square is past the number under test.
- 91 = 7 × 13 and 117 = 3 × 39 are not prime; 97 leaves a remainder with the candidates 2, 3, 5 and 7, and 11 × 11 = 121 is past it, so 97 is prime.