Primality Test: Why You Only Check to the Square Root

Contents
There's a fixed sequence of steps for checking whether a number is prime. By definition, 1 is excluded from the start. Check 2 and 3 first, then you only need to divide the remaining candidates up to the square root to get your answer.
If you're trying to understand prime-checking logic or want to verify a specific number by hand, the place where you get stuck is usually somewhere in this sequence.
Summary ① A prime is "a natural number greater than 1 whose only factors are 1 and itself," so 1 is excluded by definition. ② Once you filter out multiples of 2 and 3, the remaining candidates shrink to numbers that leave a remainder of 1 or 5 when divided by 6. ③ When n=a×b, at least one of a and b must be at or below the square root, so testing only up to the square root is enough.
The Moment You Get Stuck Checking Whether a Number Is Prime
When you check two- or three-digit numbers by hand, there comes a moment when it's unclear how far you need to divide before you can stop.
For example, say you're checking whether 91 is prime. It isn't divisible by 2 or 3, so it feels like you should keep trying 5, 7, 11, 13, and so on. Without a rule for when to stop, you'll just keep dividing forever.
You hit the same wall when solving coding problems. A problem might ask you to "write a function that checks whether n is prime," and it often comes with the hint "only divide up to the square root." But if you don't know why that works, you're just memorizing code.
If you know only the answer and not the math behind it, you can't even check your own work once the number gets a little bigger (five or six digits). Once you get the checking sequence straight, that problem goes away.
How to Check Whether a Number Is Prime by Hand
The sequence below is the same one the Prime Number Checker & Generator uses internally. Follow it in order, and you can check whether any natural number is prime by hand.
Steps 1–2: Exclude 1 and Start with 2 and 3
A prime is "a natural number greater than 1 whose only factors are 1 and itself." The only factor of 1 is itself (1), so it doesn't fit this definition and is excluded from the start. 2 and 3 are the smallest primes themselves, so they're marked prime right away.
Steps 3–4: Filter Out Multiples of 2 and 3 and Narrow the Candidates
If the remaining number is a multiple of 2 (even) or a multiple of 3, you can conclude on the spot that it isn't prime, and the value that divided it evenly (2 or 3) is shown as a factor. For example, 51 is divisible by 3, so this step marks it as composite right away.
After you remove all multiples of 2 and 3, the only numbers left are those that leave a remainder of 1 or 5 when divided by 6 (of the form 6k+1 or 6k+5).
So start at 5, then move in steps of 6: 5, 7, 11, 13, 17, 19, and so on. You only need to test the two candidates in each pair (i, i+2); the other cases don't need checking.
Step 5: Stop at the Square Root
If n = a × b, then at least one of a and b must be at or below √n. If both were greater than √n, their product would be greater than n. So if no value up to √n divides n evenly, n is confirmed prime.
Try It Yourself with 91 and 97
91 is not a multiple of 2 or 3, so it passes step 3. √91 is about 9.54, so the only candidates to try are 5 and 7.
Dividing 91 by 5 doesn't come out evenly, but 91 = 7 × 13 does. So 91 is composite, and its factor is 7.
What about 97? It also isn't a multiple of 2 or 3, and √97 is about 9.85, so the candidates are again 5 and 7. Neither divides 97 evenly, so you don't need to check any further: 97 is confirmed prime.
After you follow this sequence by hand, compare it with how the Prime Number Checker & Generator handles the same calculation instantly. It'll make more sense. Check it with our free tool, the Prime Number Checker & Generator.
Enter a number to instantly see whether it's prime and what its divisors are. Set a range and it generates the full list of primes right away. It's free.

Common Points of Confusion When Reading the Result
The result itself is clear, but there are two places where the on-screen wording is easy to misread.
The value shown as "factor" is not every factor of the number. It's the first value that divided the number evenly during the check—that is, the smallest prime factor. The actual factors of 91 are 1, 7, 13, and 91, but the screen shows only 7, the first one found during the calculation.
As numbers get larger, the number of candidates you need to test up to √n grows too. For a seven-digit number close to 1 million, √n is around 1,000, so even with the jump-by-6 optimization you still have to test hundreds of candidates before the check is done. At that point, checking by hand is practically unrealistic.
| What the screen says | What it actually means |
|---|---|
| "Not prime, factor: 7" (for 91) | It means 7 is the smallest prime factor, not a list of all of 91's factors (1, 7, 13, 91) |
| "Prime" | It means that, apart from 1 and the number itself, no value up to √n divided evenly into it |
| When the input is empty or isn't a number | It's treated as NaN and shown as an error |
Recap
- A prime is a natural number greater than 1 whose only factors are 1 and itself. 1 has only one factor, so it's excluded by definition.
- Check 2 and 3 first, then filter out their multiples. The remaining candidates shrink to numbers that leave a remainder of 1 or 5 when divided by 6.
- If n = a × b, then at least one of a and b must be at or below √n, so testing only up to √n is enough to decide whether n is prime.
- The "factor" shown on screen is not every factor of the number. It's the smallest prime factor found first during the calculation.
- The more digits a number has, the more candidates you have to test, so it's more accurate to check instantly with the Prime Number Checker & Generator than to verify by hand.
Enter a number to instantly see whether it's prime and what its divisors are. Set a range and it generates the full list of primes right away. It's free.
Frequently Asked Questions
Why isn't 1 a prime number?
A prime is a natural number greater than 1 whose only factors are 1 and itself. The only factor of 1 is itself (1), so it doesn't meet this condition. That's why 1 is treated as a separate case—neither prime nor composite.
Does the "factor" in the result show every factor of the number?
No. It shows only the first value that divided the number evenly during the calculation, which is always the smallest prime factor. 91 has four factors—1, 7, 13, and 91—but only 7 appears on screen.
Why is 2 the only even prime number?
Every even number greater than 2 is divisible by 2, so it has at least three factors: 1, 2, and itself. That means it can't be prime. 2 is the only even number with exactly two factors, 1 and 2, so it remains prime.
How is the list of primes generated?
It uses the Sieve of Eratosthenes. You list the numbers from 2 up to the range you set, then cross out multiples of the primes in order. Only the numbers left at the end are prime.
The maximum input is 1 million. If you enter a value above that, it's automatically capped at 1 million.
This article was adapted from our Korean original. Read the Korean original