What makes a number prime
A prime is a whole number greater than 1 whose only positive divisors are 1 and itself. Everything larger than 1 that is not prime is composite, meaning it can be written as a product of smaller whole numbers. The number 1 is neither: it has exactly one divisor, so it fails the definition, and it is called a unit instead.
That exclusion is not pedantry. The fundamental theorem of arithmetic says every integer above 1 factors into primes in exactly one way, up to the order of the factors. If 1 counted as prime, 12 could be written 2²×3, or 1×2²×3, or 1⁵×2²×3, and uniqueness — the property the whole theorem exists to assert — would evaporate. Every statement about factorisation would need an exception clause.
Primes are the multiplicative atoms of the integers. Divisibility, greatest common factors, least common multiples, the structure of modular arithmetic and the security of public-key cryptography all rest on how a number splits into primes, which is why so many questions reduce to a primality test somewhere along the way.
Two is the only even prime, because every other even number has 2 as a proper divisor. That makes 2 slightly awkward in statements about primes — it is common to see “odd prime” used precisely to exclude it — and it is why every practical test handles 2 as a special case before doing anything else.
How to test primality, and why the square root is enough
The direct test is trial division: try every candidate divisor and see whether any divides evenly. The refinement that makes it practical is that you never need to test past √n.
The argument is one line. Suppose n = a × b with both factors greater than 1. If both were larger than √n, their product would exceed n, which is impossible. So at least one factor is at most √n, and testing up to that bound is guaranteed to find it if it exists. For n = 97 that means testing up to 9.85, so only 2, 3, 5 and 7 — four divisions to settle the question.
Two further savings cut the work again. You only need prime candidate divisors, since any composite candidate has a prime factor that was tested earlier. And every prime above 3 has the form 6k ± 1, because 6k, 6k+2 and 6k+4 are even and 6k+3 is divisible by 3. Handling 2 and 3 separately and then stepping through 5, 7, 11, 13, 17, 19, … tests only a third of the numbers below the square root. That is what this calculator does, and it is exact: finding no divisor is a proof, not an estimate.
Where trial division stops being enough. The work grows as √n, so a twelve-digit number needs about a hundred thousand divisions and a forty-digit number needs more operations than there are atoms in a person. Cryptographic primality testing therefore uses Miller-Rabin, which tests whether n behaves the way a prime must under modular exponentiation. A single round costs about the same as one exponentiation and eliminates at least three quarters of composites; a few dozen rounds make a false positive less likely than a hardware failure. With a fixed small set of bases it is even deterministic below known thresholds. It is a different kind of test, though: it certifies that n is not composite rather than exhibiting a divisor, so it tells you nothing about how to factor a number it rejects.
Listing many primes at once calls for a different algorithm again. The sieve of Eratosthenes writes out the numbers up to a limit and crosses off multiples of each prime in turn; what survives is the prime list. It finds all primes below a million in a few milliseconds, far faster than testing each one separately, because each composite is crossed off by its own small factors rather than being independently interrogated.
Worked example: is 97 prime, and is 91?
Testing 97. First, √97 = 9.849, so no candidate above 9 can matter.
- 2? 97 is odd. No.
- 3? Digit sum 9 + 7 = 16, which is not a multiple of 3. No.
- 5? It does not end in 0 or 5. No.
- 7? 7 × 13 = 91 and 7 × 14 = 98, so 97 sits between two multiples. No.
The next candidate would be 11, but 11 > 9.849, so the search is over. 97 is prime, and four divisions proved it.
Testing 91. √91 = 9.539.
- 2? Odd. No.
- 3? Digit sum 10. No.
- 5? Ends in 1. No.
- 7? 7 × 13 = 91. Yes.
So 91 is composite, with smallest prime factor 7 and co-factor 13. It is a favourite trap question because it passes the easy tests for 2, 3 and 5 and looks prime to the eye. The lesson generalises: a number surviving the small-divisor checks is not thereby prime, and the check must run all the way to the square root.
The neighbourhood. Below 97 the nearest prime is 89, and above it is 101. The gap between those neighbours is 12, which is unusually wide down here — between 89 and 97 lie eight consecutive composites. Note also that 101 and 103 are twin primes, differing by 2, sitting right beside that long gap. Primes are irregular locally even though their density is highly predictable in aggregate.
Counting them. There are exactly 25 primes below 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Below 1,000 there are 168. Both counts are standard tabulated values and are what this calculator reproduces for those ranges.
Reading the result and the gaps around it
A composite verdict comes with a divisor, and that divisor is the useful part. Knowing that 91 is composite is worth much less than knowing it is 7 × 13. Divide out the smallest factor and test the co-factor, repeat, and you have the full prime factorisation, from which the complete divisor list, the divisor count and the divisor sum all follow.
A prime verdict here is a proof. Because the calculator exhausts every candidate up to the square root, there is no residual probability of error, unlike a probabilistic Miller-Rabin verdict. The cost is that the method has a practical ceiling; this tool takes numbers up to eleven digits, and beyond that the probabilistic tests are the only realistic option.
Gaps are locally erratic and globally predictable. The prime number theorem says the number of primes below x is asymptotically x/ln x, so near x the average spacing between primes is about ln x — roughly 7 near a thousand, 14 near a million, 21 near a billion. But individual gaps vary enormously around that average. Twin primes differing by 2 keep appearing arbitrarily far out, so far as anyone can tell, while arbitrarily long prime-free stretches are easy to construct: the n−1 consecutive numbers n!+2 through n!+n are all composite, because each is divisible by its own offset. Do not read a long gap in your range as evidence of anything.
The ratio in the reference table is the point. Divide the true count by x/ln x and the quotient drifts steadily toward 1 as x grows — 1.151 at 100, 1.084 at 100,000, 1.054 at a billion. It approaches slowly, which is why the better estimate for practical work is the logarithmic integral rather than x/ln x.
How many primes lie below each power of ten
| x | π(x) | x / ln x | π(x) ÷ (x / ln x) |
|---|---|---|---|
| 10 | 4 | 4.34 | 0.921 |
| 100 | 25 | 21.71 | 1.151 |
| 1,000 | 168 | 144.76 | 1.161 |
| 10,000 | 1,229 | 1,085.74 | 1.132 |
| 100,000 | 9,592 | 8,685.89 | 1.104 |
| 1,000,000 | 78,498 | 72,382.41 | 1.084 |
| 10,000,000 | 664,579 | 620,420.69 | 1.071 |
| 100,000,000 | 5,761,455 | 5,428,681.0 | 1.061 |
| 1,000,000,000 | 50,847,534 | 48,254,942.4 | 1.054 |
π(x) values are the standard tabulated counts. The ratio column exceeds 1 from x = 100 onward and falls steadily toward it, which is why the logarithmic integral is preferred for estimation in practice.
Mistakes and myths about primes
- Calling 1 prime. It has one divisor, not two, and admitting it would break the uniqueness of prime factorisation.
- Stopping the search too early. Passing the tests for 2, 3 and 5 proves nothing: 91 = 7 × 13 and 187 = 11 × 17 both survive those. Test every candidate up to the square root.
- Testing past the square root. Wasted effort. Every larger divisor pairs with a smaller one you have already checked.
- Believing there is a formula for the nth prime. There is no simple closed form. The polynomial n² + n + 41 famously produces primes for n = 0 to 39 and then fails at n = 40, where it gives 41².
- Assuming all Mersenne numbers 2^p − 1 with p prime are themselves prime. 2¹¹ − 1 = 2,047 = 23 × 89, so the pattern breaks at the fifth prime exponent.
- Trusting a single Fermat test. Carmichael numbers such as 561 = 3 × 11 × 17 pass the Fermat test for every base coprime to them, which is why Miller-Rabin, not the Fermat test, is the practical standard.
- Reading a long prime-free run as significant. Arbitrarily long gaps are guaranteed to exist and are easy to construct.
Why anyone needs primes
Cryptography is the reason primality testing is fast and factoring is not. RSA multiplies two large primes to make a public modulus. Generating the key requires testing candidates for primality, which Miller-Rabin does in milliseconds even at 2,048 bits; breaking the key requires factoring the product, for which no comparably fast method is known. The entire scheme rests on that asymmetry, and it is why the modular arithmetic of exponentiation and inverses sits at the centre of the subject.
Hashing and table sizing. A hash table whose size is prime distributes keys more evenly when the keys carry structure, because a composite size shares factors with regular strides in the input and collapses them onto the same buckets. Linear congruential random number generators depend on similar coprimality conditions to achieve a full period.
Engineering. Gear pairs with coprime tooth counts spread wear across every tooth combination rather than repeating the same contacts; a prime tooth count guarantees coprimality with any other count that is not a multiple of it. Cicada broods emerging on 13-year and 17-year cycles are the biological version of the same idea, minimising coincidence with shorter predator cycles.
Pure mathematics. The distribution of primes is where the deepest open questions live. The Riemann hypothesis is a statement about how far π(x) can stray from the logarithmic integral. Goldbach's conjecture — that every even number above 2 is a sum of two primes — has been verified far beyond any practical need and proved for nothing. The twin prime conjecture remains open, though the gap between infinitely many prime pairs is now known to be bounded.
Practically, the neighbouring tools do the follow-up work: prime factorisation when the verdict is composite, the greatest common factor and least common multiple when you are comparing two numbers, and long division when you want to see a divisibility test worked out digit by digit.