Prime Number
Check whether a number is prime.
About the Prime Number
A prime number divides evenly only by itself and one. This tests a number and, when it is not prime, shows what it divides by.
How to use it
- Enter a whole number.
- Read whether it is prime.
- If not, the factors are listed.
The formula
A prime number has exactly two distinct divisors: 1 and itself. To test one, you do not need to try every smaller number — only those up to its square root.
n is prime if no integer d where 2 ≤ d ≤ √n divides n exactly
The square root limit follows from a simple observation. If n has a factor larger than √n, the matching factor must be smaller than √n, and you would have found it already. For 97, testing only 2, 3, 5 and 7 settles the question, because √97 is about 9.85.
That shortcut is the difference between a test that is instant and one that is not. Checking a 10-digit number by brute force means billions of divisions; with the square root limit it means about 50,000.
Worked examples
| Number | √n | Divisors tested | Result |
|---|---|---|---|
| 97 | 9.85 | 2, 3, 5, 7 | prime |
| 91 | 9.54 | 2, 3, 5, 7 | not prime — 7 × 13 |
| 2 | 1.41 | none | prime — the only even one |
| 1 | 1.00 | none | not prime — only one divisor |
91 is the instructive row. It looks prime, it is odd, it resists the obvious tests, and it is 7 × 13. This is why a proper check matters — numbers ending in 1, 3, 7 or 9 that survive a casual glance are exactly where composite numbers hide. Note also that testing stops at 7 in both cases: 11 is already above √97, so anything it could reveal would have been caught earlier.
Common mistakes
- Thinking 1 is prime. It has only one divisor, itself, and the definition requires exactly two. Excluding it is not arbitrary — if 1 were prime, every number would have infinitely many factorisations and the fundamental theorem of arithmetic would fail.
- Assuming all primes are odd. 2 is prime, and it is the only even one. Every other even number is divisible by 2 by definition.
- Testing every number up to n. Unnecessary. Stop at √n. Beyond that, any factor would have a partner below the root that you already checked.
- Believing odd numbers ending in 1, 3, 7 or 9 are usually prime. Primes thin out as numbers grow. Around a million, only about one number in fourteen is prime, and most odd-looking candidates are composite.
Terms explained
- Prime number
- A whole number greater than 1 with no divisors except 1 and itself.
- Composite number
- A whole number above 1 that is not prime — it has at least one additional factor.
- Factor
- A number that divides another exactly, leaving no remainder.
- Prime factorisation
- Expressing a number as a product of primes, such as 60 = 2² × 3 × 5. Every number above 1 has exactly one.
- Sieve of Eratosthenes
- An ancient method for listing primes by repeatedly crossing out multiples. Still the fastest way to find all primes below a limit.
- Twin primes
- Two primes separated by 2, such as 11 and 13. Whether there are infinitely many is a famous unsolved problem.
Common questions
- Why is 1 not a prime number?
- Because a prime must have exactly two distinct divisors, and 1 has only one. Excluding it keeps prime factorisation unique — otherwise you could pad any factorisation with as many 1s as you liked.
- Is 2 really prime?
- Yes, and it is the only even prime. Every larger even number has 2 as a factor, which disqualifies it immediately.
- How do I check a large number quickly?
- Test divisibility only up to its square root, and only by primes. For anything genuinely large, probabilistic tests such as Miller-Rabin are what software actually uses.
- How many prime numbers are there?
- Infinitely many — Euclid proved it around 300 BC with an argument short enough to fit in a paragraph. They do get sparser, but they never run out.
- What is the largest known prime?
- It is a Mersenne prime with tens of millions of digits, found by the distributed GIMPS project. The record is broken every few years.
- Why do primes matter outside mathematics?
- Public-key cryptography depends on them. Multiplying two large primes is easy; recovering them from the product is not, and that asymmetry is what secures most online communication.
- What is the Sieve of Eratosthenes?
- List the numbers, then repeatedly cross out multiples of each prime you find. Whatever survives is prime. It is over two thousand years old and still the standard method for generating a list.
- Is there a formula that generates primes?
- No simple one. Several formulas produce primes for a while and then fail — n² − n + 41 is famously prime for n up to 40, then breaks at 41.