In this article
Is 91 a prime number? Most people pause, think it looks prime, and say yes. It is not: 91 = 7 × 13. Primes are the atoms of arithmetic, and the surprising thing is how often our eyes get them wrong. This guide gives you a reliable way to test any number, a picture of how primes are spread, and a look at the real-world job they do every time you pay online.
What makes a number prime
A number is prime if it has exactly two divisors: 1 and itself. 7 is prime (only 1 × 7). 9 is not (3 × 3 is another way to build it). Numbers with more divisors are called composite. The number 1 has only one divisor, so it is neither prime nor composite, and 2 is the only even prime, since every larger even number is divisible by 2.
Why do mathematicians care? Because of a basic fact: every whole number above 1 can be written as a product of primes in exactly one way (ignoring order). 60 = 2 × 2 × 3 × 5, and no other combination of primes gives 60. Primes are the building blocks, and the multiplication table is built from them.
| Numbers | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 + | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 10 + | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 20 + | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 30 + | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 40 + | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 50 + | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 60 + | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 70 + | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 80 + | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 90 + | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
There are 25 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. Look for the traps: 51 = 3 × 17, 57 = 3 × 19, 87 = 3 × 29 and 91 = 7 × 13 all look prime but are not.
| Looks prime… | But it is | Quick tell |
|---|---|---|
| 51 | 3 × 17 | Digits add to 6, so 3 divides it |
| 57 | 3 × 19 | Digits add to 12 |
| 87 | 3 × 29 | Digits add to 15 |
| 91 | 7 × 13 | Needs the 7 times table |
| 119 | 7 × 17 | Needs the 7 times table |
The digit-sum rule for 3 catches many fakes. 7 and 13 are the usual troublemakers.
How to test a number: stop at the square root
The obvious way to test n is to try dividing by every number up to n. That is slow. Luckily there is a shortcut. If n = a × b, then one of the two factors must be at most √n. (If both were bigger than √n, their product would be bigger than n.) So if no divisor appears up to √n, none will appear after it, and the number is prime.
- 1Find the square root√1,000,003 is about 1,000.0015. Only divisors up to 1,000 matter.
- 2Try only primesThere are 168 primes below 1,000, so at most 168 divisions, not a million.
- 3Stop at the first hitIf any prime divides evenly, the number is composite. None does here.
- 4Conclude1,000,003 is prime. A shortcut turned a million checks into 168.
The shortcut gets better with size: the work grows with the square root of the number, not the number itself.
Multiplying n by 1,000 multiplies the work by about 31.6. Even so, this method is hopeless for the 600-digit numbers used in cryptography, which use cleverer tests.
Finding all the primes: the sieve
Suppose you want every prime up to 100 at once. An old method called the Sieve of Eratosthenes, over two thousand years old, does it without any division at all. Write down the numbers, then repeatedly cross out the multiples of each surviving number. What is left is prime.
- 1List 2 to 100Start with every number except 1.
- 2Keep 2, cross out its multiples4, 6, 8, 10 and so on disappear.
- 3Keep 3, cross out its multiples9, 15, 21 and all other odd multiples go.
- 4Keep 5 and 7, repeatAfter 7 you can stop, because 11 × 11 is already bigger than 100.
- 5Read what survivedThe 25 numbers left are exactly the primes below 100.
A computer can run the same sieve on ten million numbers in a fraction of a second. That is how the prime counts in this article were checked.
Primes never end, but they thin out
Euclid’s proof that there are infinitely many primes is only a few lines: assume there is a largest prime, multiply all primes together and add 1; the result is not divisible by any of them, so there must be a new prime. Beautiful, short and still airtight.
Yet primes become sparser as you climb. In the first hundred numbers, a quarter are prime. In each later hundred, there are fewer. Here is the count for each century up to 1,000.
The counts total 168. The trend is downward, but not smoothly: 16 and then 16 and then 17. Primes are irregular in the small and predictable in the large.
- 104 primes2, 3, 5, 7. That is 40% of the numbers.
- 10025 primes25% of the numbers.
- 1,000168 primes16.8%. Roughly one in six.
- 10,0001,229 primes12.3%. Roughly one in eight.
- 1 million78,498 primes7.85%. Roughly one in thirteen.
- 10 million664,579 primes6.65%. Roughly one in fifteen.
The prime number theorem says the share near x is about 1 divided by the natural logarithm of x. The estimate is close and gets relatively better as x grows. Primes thin out, but very slowly.
Odd patterns: twin primes and open questions
Primes that differ by 2 are called twin primes: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43). Whether there are infinitely many of them is still unproven, as is the Goldbach conjecture, which says every even number above 2 is the sum of two primes (4 = 2 + 2, 10 = 3 + 7, 100 = 3 + 97). Computers have checked it for enormous ranges without a counterexample, yet nobody has a proof.
Primes are an area where a child can ask a question that stumps experts.
The job primes do for your bank
Here is the practical payoff. Multiplying two primes is easy: 101 × 103 = 10,403 takes a moment. Going the other way, finding the two primes that produce 10,403, takes real work. With small numbers it is just a puzzle. With numbers hundreds of digits long, the best known methods on ordinary computers would need an impractical amount of time.
That one-way difficulty is the heart of RSA, one of the systems that protects secure websites. A common key has 2,048 bits, a number of about 617 digits, built from two primes of roughly 309 digits each. Your browser and the server can use the public product freely. Only someone who knows the two primes can reverse the process.
- Two 309-digit primes
- A fraction of a second
- Produces a 617-digit number
- No known fast method on classical computers
- Brute force is far beyond practical computing power
- Quantum computers could change this, which is why new methods are being developed
Security does not come from hiding the method, only from this gap in effort. See what a hash is and password entropy for other forms of the same idea.
Finding the primes is quick. Recovering them from the product, without being told, is what nobody can do in practice.
How do you find a 309-digit prime in the first place? By trial and error with a fast probabilistic test. Roughly 1 in 710 numbers of that size is prime (1 ÷ ln N), or 1 in about 355 if you skip even numbers. A computer simply picks random odd numbers and tests them until one passes, which takes a fraction of a second.
Practice and take-aways
- Is 221 prime? √221 is about 14.9. Try 2, 3, 5, 7, 11, 13. 13 × 17 = 221, so it is not prime.
- Is 97 prime? √97 is about 9.8. Try 2, 3, 5, 7. None divides, so it is prime.
- Write 84 as a product of primes: 84 = 2 × 2 × 3 × 7.
- Which is the only even prime? 2, because every other even number is divisible by 2.
Primes combine the simplest definition in mathematics with some of the hardest unsolved questions. They thin out gently, hide behind clever fakes like 91, and quietly keep your payments private. Paste any number in the checker above and see for yourself. If you like number systems, the binary, hex and decimal guide is a natural next step.
Questions people ask
Is 1 a prime number?
No. A prime has exactly two divisors, 1 and itself, and 1 has only one divisor. This convention keeps the unique-factorisation rule true.
Is 2 prime?
Yes, and it is the only even prime. Every other even number is divisible by 2, so it has at least three divisors.
How do I check if a number is prime?
Divide it by every prime up to its square root. If none divides evenly, the number is prime.
How many primes are there below 100?
25: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
Why are prime numbers used in encryption?
Multiplying two large primes is quick, but recovering them from the product is extremely hard with known methods. Systems such as RSA are built on that gap.
Are there infinitely many primes?
Yes. Euclid proved it over 2,000 years ago: no list of primes can be complete, because multiplying them and adding 1 produces a number with a prime factor outside the list.