Prime Number Checker & Factorizer
Check whether a number is prime and see its prime factorisation and divisors, with the reason only square roots need testing.
Why this answers instantly for a twelve-digit number
The obvious way to test whether n is prime is to try dividing it by everything below it. For 999,983 that is 999,981 divisions. Two observations cut that down enormously, and both are worth stating because they are the whole reason primality testing is easy while factoring is hard.
The first is that you can stop at the square root. If n = a · b then one of a and b is at most √n, so a factor above the root always has a partner below it and you would have found it already. That takes 999,983 from 999,981 divisions to 998. The second is that you only need to try primes — anything divisible by 6 was already caught by 2. There are 168 primes below 1,000, so the real cost is 168 divisions rather than 999,981: about 5,952 times less work.
That saving grows as the numbers do, which is why the tool above can answer for an eighteen-digit number without pausing while it cannot always factor one. It uses a stronger method still — a Miller–Rabin test, which decides primality without finding any factor at all. Deciding whether a number has a factor turns out to be far cheaper than finding one, and essentially all of public-key cryptography lives in that gap.
Primes thin out, but far more slowly than people expect
Primes get rarer as numbers get larger, and the usual guess is that they rapidly run out. They do not. The density falls like 1 ⁄ ln(n), and a logarithm is about as slow as a falling quantity gets — a hundredfold increase in range costs you roughly a halving.
| Up to | Primes | Density | 1 ⁄ ln(n) predicts |
|---|---|---|---|
| 10 | 4 | 40.0% | 43.4% |
| 100 | 25 | 25.0% | 21.7% |
| 1,000 | 168 | 16.80% | 14.48% |
| 10,000 | 1,229 | 12.29% | 10.86% |
| 100,000 | 9,592 | 9.59% | 8.69% |
| 1,000,000 | 78,498 | 7.85% | 7.24% |
One in four numbers below a hundred is prime; one in thirteen below a million. Those counts are not estimates — 25, 168, 1,229, 9,592 and 78,498 are the documented values of π(x), and the sieve behind this page is checked against every one of them.
The averages hide how uneven the spacing is. Below a million the mean gap between consecutive primes is about 12.7, but the largest is 114, immediately after 492,113 — nearly nine times the average spacing there, with a hundred and thirteen composite numbers in a row. At the other extreme, 8,169 pairs sit just 2 apart. Arbitrarily long prime-free runs are easy to construct, too: n! + 2, n! + 3, … n! + n are all composite by inspection, so a gap of any length you like exists somewhere. Whether the twins also go on forever is still an open question.
How to use
- Enter a whole number.
- Read whether it is prime.
- Inspect the factorisation and divisor list.
- Try a large number to see the factorisation slow down.
Frequently asked questions
Is 1 a prime number?
No, by definition and for good reason. A prime has exactly two distinct divisors, and 1 has only one. Excluding it is what makes the fundamental theorem of arithmetic work — every integer above 1 factors into primes in exactly one way, which would fail if 1 counted, since you could insert any number of 1s.
Is 2 really prime?
Yes, and it is the only even prime. Every other even number is divisible by 2 and therefore has a third divisor. Mathematicians occasionally call 2 the oddest prime for exactly this reason.
Why only test divisors up to the square root?
Because divisors come in pairs that multiply to the number, and in every pair one member is at or below the square root. If nothing at or below the square root divides it, nothing above can either. This turns an impractical search into a quick one.
How many primes are there?
Infinitely many, proved by Euclid around 300 BC with an argument still taught today: assume a complete list, multiply them all together and add 1, and the result is divisible by none of them. They do thin out as numbers grow, roughly in proportion to the natural logarithm.
What are twin primes?
Pairs differing by 2, such as 11 and 13. Whether infinitely many exist is a famous unsolved problem, though a 2013 breakthrough proved that infinitely many prime pairs exist within some bounded gap — the bound has since been pushed down substantially, but not to 2.
Why does factorisation matter for security?
Because multiplying two large primes is easy while recovering them from the product is not. RSA encryption rests on that asymmetry. A sufficiently capable quantum computer would break it using Shor's algorithm, which is why post-quantum cryptography is now being standardised.
🔒 This tool runs entirely in your browser. Nothing you enter is uploaded, logged, or stored.