Checking for primes: why you stop at the square root
A prime number is a whole number of 2 or more whose only exact divisors are 1 and itself. Testing one by hand seems like it should mean trying every smaller number. It does not — you can stop at the square root, and the reason is worth understanding because it makes the job dramatically shorter.
Why the square root is enough
If a number n divides evenly by something, that division has a partner. When 84 divides by 4, the partner is 21, because 4 × 21 = 84. Factors always arrive in pairs.
Now: in any such pair, one member must be at or below the square root of n, and the other at or above it. They cannot both be above — their product would overshoot n. They cannot both be below, for the same reason in reverse.
So if a factor exists at all, the smaller half of some pair is at or below √n. Test everything up to there, find nothing, and there is nothing to find above it either. For 97, √97 is about 9.85, so you need only test up to 9 — ten candidates instead of ninety-six.
A real example: is 97 prime?
Test the numbers up to 9:
- 2? 97 is odd. No.
- 3? Its digits sum to 16, which is not a multiple of 3. No.
- 5? It ends in 7. No.
- 7?
7 × 13 = 91,7 × 14 = 98. It skips over 97. No.
(4, 6, 8 and 9 need no separate test: anything divisible by 4 is divisible by 2, and anything divisible by 9 is divisible by 3. Once the primes are ruled out, their multiples are too.) Nothing divides it, so 97 is prime.
A real example: is 91 prime?
91 looks prime. It is odd, its digits sum to 10 so 3 is out, and it does not end in 0 or 5. Many people stop there and call it prime. But √91 is about 9.54, so 7 is still in range — and 7 × 13 = 91. It is not prime.
91 is the classic trap precisely because the first three tests all pass. Stopping early is a different mistake from stopping at the square root: one is a rule, the other is giving up.
Factorising: keep going after the first hit
Finding one factor answers "is it prime?" but not "what is it made of?". For the full prime factorisation, divide out each factor and continue with what is left. For 84:
84 ÷ 2 = 4242 ÷ 2 = 21- 21 is not even;
21 ÷ 3 = 7 - 7 is prime, so stop.
So 84 = 2 × 2 × 3 × 7. Multiply back to check: 2 × 2 = 4, 4 × 3 = 12, 12 × 7 = 84. Correct. Note 2 appears twice — dividing a factor out once is not enough, because it may divide again.
A larger one, 360: divide by 2 three times (360, 180, 90, 45), then by 3 twice (45, 15, 5), leaving 5. So 360 = 2 × 2 × 2 × 3 × 3 × 5. Checking: 8 × 9 × 5 = 360. Every whole number above 1 has exactly one such factorisation, which is why it is a fingerprint rather than merely one description among several.
The numbers that are neither
1 is not prime. It has only one divisor, itself, where a prime needs exactly two distinct ones. This is a definition chosen deliberately rather than an oversight: if 1 counted as prime, then 12 could be written as 2 × 2 × 3 or 1 × 2 × 2 × 3 or with any number of 1s, and the "exactly one factorisation" rule that makes primes useful would collapse. 0 and negative numbers have no prime factorisation either.
Where this stops being practical
Trial division to the square root is fine for everyday numbers and hopeless for large ones. Testing a 600-digit number this way would mean around 10300 divisions — not slow, but impossible. Cryptography depends on exactly that gap: multiplying two large primes is instant, and recovering them from the product is not.
Run your own numbers
The free Prime Checker tests divisibility up to the square root and returns both the verdict and the full prime factorisation, entirely on your device.