91 looks prime. It is not.
91 is the classic trap.
Odd. Ends in 1. Survives division by 2, 3 and 5. Then 7 × 13 = 91. The board above stamps each composite with its smallest factor in the corner, so 91 wears a 7. A prime such as 89 wears nothing. Only 1 and 89 divide it.
A prime is a whole number above 1 with exactly two divisors, 1 and itself. A composite has three or more. Zero and one sit outside both groups on purpose: count 1 as prime and 6 gains endless factorizations (2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3), which breaks the rule that every number splits into primes in exactly one way.
- Prime
- Exactly two divisors. 2, 3, 5, 7, 11.
- Composite
- Three or more divisors. 4, 6, 91.
- Twin primes
- Two primes with a gap of 2, like 71 and 73. The inspector tags them.
- Mersenne prime
- A prime one below a power of two, such as 31 (2⁵ − 1) or 8,191 (2¹³ − 1). Nearly every record-sized prime is this type.
- Carmichael number
- A composite that fools the Fermat primality test for every base sharing no factor with it. 561 is the smallest.
Stop at the square root
Testing 221 by hand? Do not divide by every number up to 220.
Factors come in pairs that multiply to the target. One member of every pair sits at or below the square root, so the search ends there. √221 is about 14.9, which leaves 2, 3, 5, 7, 11 and 13 to try. The last one hits: 13 × 17 = 221.
| Number | √n | Primes to test | Outcome |
|---|---|---|---|
| 91 | 9.54 | 2, 3, 5, 7 | 7 × 13, composite |
| 97 | 9.85 | 2, 3, 5, 7 | No divisor, prime |
| 221 | 14.87 | 2, 3, 5, 7, 11, 13 | 13 × 17, composite |
| 1,009 | 31.76 | The 11 primes up to 31 | No divisor, prime |
| 9,007,199,254,740,881 | 94,906,265.6 | Too many for paper | Miller-Rabin says prime |
Software uses the same cutoff. Trial division clears a nine-digit number in a blink. Near 15 digits it starts to drag, which is why this page switches to Miller-Rabin for primality and keeps trial division only for splitting composites into factors.
Pulling IDs out of a spreadsheet column? Strip repeats with the remove duplicates tool first, though the list tab also merges repeats by itself.
Primes thin out, slowly
Euclid showed around 300 BC that primes never run out. They do get rarer. Near a number n, roughly one integer in ln(n) is prime.
| Up to | Primes | Share | 1/ln n estimate |
|---|---|---|---|
| 100 | 25 | 25% | 21.7% |
| 1,000 | 168 | 16.8% | 14.5% |
| 10,000 | 1,229 | 12.3% | 10.9% |
| 100,000 | 9,592 | 9.6% | 8.7% |
| 1,000,000 | 78,498 | 7.8% | 7.2% |
| 1,000,000,000 | 50,847,534 | 5.1% | 4.8% |
The estimate runs low for small numbers and closes in as they grow. Scan 1 to 50,000 above and watch the bars sag toward the right edge. The Share tile prints the estimate under its own figure, so you see the gap on any window you pick.
One pattern holds without exception. Past 2 and 5, every prime ends in 1, 3, 7 or 9. The reverse fails: 21, 27 and 49 all end in one of those digits.
Where this page stops
- Ranges: the end value tops out at 1,000,000,000,000, with 50,000 numbers per scan. A segmented sieve does the work, so a window near a trillion runs about as fast as one near 100.
- Lists: up to 10,000 different whole numbers, each at most 9,007,199,254,740,991. Anything else is skipped and named in a banner above the board. Decimals, negatives and entries like
1,000with a thousands comma are all skipped, since the comma splits them. - Verdicts: Miller-Rabin with 12 fixed bases is exact below 3.3 × 10²⁴. At 16 digits the answer is a proof, not a probability.
- Factoring: trial division with a 3 second cap. Two near-equal 8-digit primes multiplied together are the slow case, around half a second here. If the cap hits, the inspector shows the unsplit remainder in a dashed box.
The Fermat fools sample loads 561, 1,105, 1,729 and four more Carmichael numbers. Each passes a common shortcut test and each is composite. Click them and the inspector tags the family, because every one splits into at least three distinct primes.
Where primes earn their keep
- Hash tables: a prime bucket count spreads keys that arrive in regular steps of 8 or 10, where a round size piles them into a few buckets.
- Gears: tooth counts with no shared factor make every tooth meet every other before the pattern repeats, which evens out wear. The GCD calculator confirms two counts share nothing.
- Cicadas: periodical broods surface every 13 or 17 years. Both are prime, which keeps their cycles from lining up with most predators.
- Cryptography: RSA multiplies two huge primes. Security rests on splitting the product being slow, the same job the inspector does at toy scale.
Need the whole divisor list or factor pairs for one number? The factor calculator prints them. To watch the elimination step by step, the Sieve of Eratosthenes animates it for numbers up to 1,000. Numbers equal to the sum of their proper divisors, like 6 and 28, belong to the perfect number finder.
Myths worth retiring
| Claim | Verdict | Counterexample |
|---|---|---|
| Odd numbers are prime | False | 9, 15, 91 |
| 2 is not prime because it is even | False. It has exactly two divisors. | 2 is the only even prime |
| A last digit of 1, 3, 7 or 9 means prime | Necessary past 5, never sufficient | 21, 27, 49 |
| 1 is the first prime | False by convention | Unique factorization would break |
| Every even number above 2 is a sum of two primes | Checked past 4 × 10¹⁸, never proven | None found (Goldbach) |
Splitting a column of numbers by parity first? The even and odd filter removes half the candidates before you paste.
