Is it prime? You only need to test up to the square root

Is 91 prime? It does not divide by 2, 3 or 5, so many people say yes. But 91 = 7 × 13, so it is not prime. Here is a method that catches numbers like this without testing every possible divisor.

The rule

To check whether a number n is prime, divide it only by the primes up to the square root of n. If none of them divides n exactly, n is prime. If one does, n is composite.

Example 1: is 97 prime?

The square root of 97 is a little under 10, because 10² = 100.
The primes up to 10 are 2, 3, 5 and 7.
97 is odd, so 2 does not divide it. Its digit sum is 16, so 3 does not divide it. It does not end in 0 or 5, so 5 does not divide it. And 7 × 13 = 91, so 97 leaves remainder 6 on division by 7.

None of the four primes divides 97, so 97 is prime.

Example 2: the trap of 91

The square root of 91 is a little under 10 as well (9² = 81 and 10² = 100). The primes to test are again 2, 3, 5 and 7. The first three fail, but 7 × 13 = 91, so 91 is composite. This is the number that fools people, because 91 passes all the quick tests for 2, 3 and 5.

Why it works

Suppose n is composite, so n = a × b with 1 < a ≤ b. Then a × a ≤ a × b = n, which means a² ≤ n and so a ≤ √n. In other words, every composite number has a factor that is at most its square root. If you find no factor up to √n, there cannot be one beyond it, because a factor larger than √n would be paired with a smaller one that you would already have found.

For 91 the pair is 7 and 13. The smaller one, 7, is below √91 ≈ 9.5, exactly where the rule says it must be.

Why only primes need to be tested

If a composite number such as 4 or 9 divided n, then so would its prime factors (2 or 3), which you have already tested. This is the idea behind the Fundamental Theorem of Arithmetic in Class 10: every composite number is a product of primes.

Try it yourself

Is 101 prime? Which primes do you need to test?
Is 119 prime? Is 127 prime?
Is 169 prime? (Hint: look at 13 × 13.)

Answers: 101 is prime (test 2, 3, 5 and 7). 119 = 7 × 17, so it is not prime. 127 is prime (test 2, 3, 5, 7 and 11, since 11² = 121 is below 127 but 13² = 169 is above it). 169 = 13 × 13, so it is not prime. Primes and factorisation are part of the Real Numbers chapter, and you can start with the Class 10 chapters. When you want practice, build a fresh test with the Practice Generator.