How to Tell if a Number Is Prime: The Square-Root Rule

A prime number is a whole number greater than 1 with exactly two divisors: 1 and itself. 2, 3, 5, 7 and 11 are prime. 1 is not prime, because it has only one divisor, and 2 is the only even prime.

The square-root rule

You never need to test every number below n. If n = a × b, at least one of a and b must be √n or smaller. So it is enough to test the primes up to √n.

Is 221 prime? √221 ≈ 14.9, so test 2, 3, 5, 7, 11 and 13. The last one works: 221 = 13 × 17, so 221 is composite.

Is 211 prime? √211 ≈ 14.5, so test the same primes. None of 2, 3, 5, 7, 11 or 13 divides 211, so 211 is prime. Six divisions settled it.

Quick checks before you divide

• Even number: divisible by 2.
• Digit sum divisible by 3: the number is divisible by 3. 1,011 has a digit sum of 3, so 1,011 = 3 × 337.
• Ends in 0 or 5: divisible by 5.
• Alternating digit sum divisible by 11: divisible by 11.

These rules rule out most composite numbers in seconds. Numbers like 91 = 7 × 13 and 51 = 3 × 17 look prime but fail the test.

The 6k ± 1 pattern

Every prime greater than 3 is one more or one less than a multiple of 6: 5, 7, 11, 13, 17, 19 and so on. That is why computer programs only test divisors of the form 6k − 1 and 6k + 1. The reverse is not true: 25 = 24 + 1 is not prime.

Prime factorization

Every composite number splits into primes in exactly one way. Divide by the smallest prime repeatedly: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5. So 360 = 2³ × 3² × 5.

Primes under 100

There are 25: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

Tip Primes protect your online banking. Common encryption multiplies two huge primes together; the product is easy to compute but extremely hard to split back into its factors.

Frequently asked questions