A prime has exactly two distinct factors: 1 and itself. To check by hand, try dividing by each prime up to the square root — if none of them divides it, nothing does, because two factors both above the square root would multiply to more than the number. 97 needs only 2, 3, 5 and 7 tried. 91 fails at 7, and 7 × 13 is the proof.
How primality is decided
The schoolbook method is trial division: try every prime up to the square root. It is exact, and it is what the page runs on smaller numbers to find a divisor when one exists.
Past a certain size it becomes slow, and the standard replacement is the Miller-Rabin test. Used with random witnesses it is probabilistic. Used with a FIXED set of small witnesses it is provably exact below a known bound — the twelve primes up to 37 settle every number below 3.3 × 10²⁴.
That is the version here, and it is why this page says “prime” rather than “probably prime”. The limit of twenty-five digits sits well inside the proven range.
Why 1 is not prime
The definition asks for exactly TWO distinct factors. 1 has one. That is the whole reason, and it is a count rather than a convention.
There is a deeper cost to including it. Unique factorisation says every number above 1 is a product of primes in exactly one way. If 1 were prime, 12 could be 2 × 2 × 3, or 1 × 2 × 2 × 3, or with any number of 1s — and the theorem that makes primes useful would need a clause bolted on.
1 was in fact called prime by some mathematicians into the early twentieth century. It stopped because keeping it cost more than it was worth.
The 6k ± 1 shape
Every prime above 3 is one away from a multiple of six. Not a coincidence: of the six residues modulo 6, four are immediately disqualified.
6k is divisible by 6. 6k + 2 and 6k + 4 are even. 6k + 3 is divisible by 3. That leaves only 6k + 1 and 6k − 1, and every prime above 3 must be one of them.
It is a real speed-up for a hand search, since it lets you skip five numbers in every six. It is not a test for primality — 25 and 35 are both of that shape and neither is prime — it only narrows where to look.
Carmichael numbers, and why the test is deterministic
Fermat’s little theorem gives a quick test: if n is prime then a^(n−1) leaves remainder 1 modulo n for any a not divisible by n. Composite numbers usually fail it, so it looks like a cheap primality check.
Carmichael numbers pass it for every a coprime to them while being thoroughly composite. 561 is the smallest — it is 3 × 11 × 17 — and there are infinitely many.
Miller-Rabin closes the hole by looking at the square roots of 1 along the way rather than only the endpoint, and no composite survives it against the fixed witness set below the proven bound. Enter 561 above and it is correctly rejected, with 3 named as the divisor.
Gaps, twins and how primes thin out
Primes get rarer as numbers grow. Around n, roughly one number in ln(n) is prime — about one in seven near 1000, one in twenty near 500 million.
They still cluster. Twin primes, two apart, keep appearing as far as anyone has looked, and whether they do so forever is one of the oldest open questions in mathematics. This page says when your number is one of a twin pair.
Gaps can also be made arbitrarily long: the numbers from n! + 2 to n! + n are all composite, which gives a run of n − 1 with no prime in it. Both facts are true at once, which is what makes the distribution interesting.
Why anyone needs large primes
RSA encryption picks two large primes, multiplies them, and publishes the product. Anyone can multiply; nobody can factorise a six-hundred-digit product back into its two primes in any reasonable time.
Notice what that requires: primality must be EASY to check and factorisation must be HARD. Both are true, and the gap between them is the entire foundation. Miller-Rabin is what makes the first half work at that scale.
Hash tables use primes for a smaller reason — a prime table size spreads keys more evenly, because a key pattern sharing a factor with the size collides systematically.
Sources and methodology
Deterministic Miller-Rabin bounds are a published result; these are the references.
Method. A deterministic Miller-Rabin test with the twelve-witness set that is proven to give the exact answer for every number below 3.3 × 10²⁴ — far past the twenty-five digit limit this page accepts. That is why the verdict is stated as prime rather than probably prime. When the answer is composite and the number is small enough, trial division runs alongside to find the smallest divisor, because a named witness is a proof the reader can check and a bare verdict is not. That engine is verified on every change against 64 hand-written assertions, including that the test agrees with plain trial division on every number under thirty thousand, and that it correctly rejects the Carmichael numbers that defeat the naive Fermat test. The count and the per-case breakdown are published on the formula verification page.
Read the guide
If the answer is no and you want the full breakdown, the Prime Factorization Calculator gives every prime with its power. If you want everything that divides the number rather than just the primes, the Factor Calculator lists them in pairs.