On this page
To test 221 for primality you need six divisions at most, and the last digit settles two of them. Here is the method, the shortcuts that speed it up, and where it stops working.
Why do you only need to check up to √n?
If n is composite, write it as a × b. If both factors exceeded √n, their product would exceed n. So a composite n always has a factor no bigger than √n, as the Wikipedia article on trial division explains.
The Prime Pages put the method in one line: to test n, divide by all the primes less than its square root. You only need primes: if 9 divides n, then 3 does too.
There are 25 primes up to 100, according to the Prime Pages count of primes. Those 25 are enough to test any four-digit number, since its square root is below 100.
What are the quick divisibility tests for 3, 7, 11 and 13?
Beyond the last-digit tests for 2 and 5, the Wikipedia article on divisibility rules lists these:
3: add the digits. If the sum is a multiple of 3, so is the number.
7: take off the last digit, double it, and subtract it from what is left. For 91: 9 − 2 = 7, so 7 divides 91.
11: take the alternating sum of the digits (+ − + from the right). For 209: 9 − 0 + 2 = 11, so 11 divides 209.
13: take off the last digit, multiply it by 4, and add it to what is left. For 221: 22 + 4 = 26, so 13 divides 221.
The same source lists a block test for 7 and 13: take the alternating sum of three-digit blocks from the right. Since 1001 = 7 × 11 × 13, it tests 11 too. For 10,023: 23 − 10 = 13, so 13 divides it (13 × 771), but 7 and 11 do not.
How do you spot composites like 91 and 221 quickly?
These pass every easy test (odd, not ending in 5, digit sum not a multiple of 3), so learn them by sight:
91 = 7 × 13
143 = 11 × 13
187 = 11 × 17
221 = 13 × 17
247 = 13 × 19
323 = 17 × 19
A second trick: look for a nearby perfect square. If n = a² − b², then n = (a − b)(a + b). So 91 = 100 − 9 = 7 × 13, 221 = 225 − 4 = 13 × 17, and 899 = 900 − 1 = 29 × 31. It catches products of two close factors, which trial division finds last.
For the basics, see our guide to primes, co-primes and divisibility tests in Class 6; once you have the factors, counting divisors with prime factorisation shows what to do next.
Worked example: is 211 prime?
Find the limit. 14 × 14 = 196 and 15 × 15 = 225, so √211 is between 14 and 15. Test primes up to 13.
2 and 5: 211 is odd and ends in 1. No.
3: digit sum 2 + 1 + 1 = 4. No.
7: 21 − 2 = 19. No.
11: 1 − 1 + 2 = 2. No.
13: 21 + 4 = 25. No.
So 211 is prime. Now try 667: it is 676 − 9 = 26² − 3² = 23 × 29. The square trick takes one line; trial division would need nine primes.
How do you check if a large number is prime?
Trial division's running time grows exponentially with the number of digits, according to the Wikipedia article on trial division. The Prime Pages say that once n has 25 or more digits, dividing by the primes below its square root is impractical, and at 200 digits it is impossible.
Computers use tests that do not search for a factor. One uses Fermat's little theorem: if a to the power n − 1 does not leave remainder 1 when divided by n, then n is composite. It can be fooled: the Prime Pages page on Fermat's test notes that 341 = 11 × 31 passes it for base 2.
In 2004, Manindra Agrawal, Neeraj Kayal and Nitin Saxena of IIT Kanpur published PRIMES is in P in the Annals of Mathematics, giving a deterministic polynomial-time algorithm that decides whether a number is prime or composite.
The numbers in most school and olympiad questions are small enough for √n, the divisibility tests and the square trick; our IOQM number theory guide shows where they turn up. If you get stuck, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, and the Fermi Concept Library gives each mathematics concept its own lesson.
Next time, find √n first, then test the primes up to it.
