What a Prime Number Is, and Why 1 Doesn't Count
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, you can't form it by multiplying two smaller natural numbers together. The first few: 2, 3, 5, 7, 11, 13...
15: divisors are 1, 3, 5, 15 → composite (3 × 5 = 15)
2: divisors are 1 and 2 only → prime (the only even prime)
Why is 1 excluded? It's not arbitrary - it's there to protect the Fundamental Theorem of Arithmetic, which says every integer greater than 1 has a unique prime factorisation. If 1 were prime, that uniqueness falls apart: 12 = 2² × 3 = 1 × 2² × 3 = 1 × 1 × 2² × 3, and on forever. Each would be a perfectly valid factorisation. So 1 gets its own category - it's called a unit, neither prime nor composite. The "greater than 1" part of the definition isn't a quirk; it's what makes the whole system hold together.
Numbers with more than two divisors are called composite. Every composite number breaks down into a product of primes - those primes are its prime factors.
The Sieve of Eratosthenes: Still One of the Best Methods
The Sieve of Eratosthenes goes back to around 240 BCE, and it's still one of the most efficient ways to find all primes up to a given limit. The idea is elegant: instead of testing each number individually, you just cross out multiples.
The procedure for finding all primes up to N:
- Write every integer from 2 to N.
- Start at 2 (the first prime). Mark every multiple of 2 that is greater than 2 as composite: 4, 6, 8, 10, …
- Move to the next unmarked number (3). Mark all multiples of 3 greater than 3: 6, 9, 12, 15, …
- Move to the next unmarked number (5). Mark all multiples of 5 greater than 5: 10, 15, 20, 25, …
- Continue until you reach a number whose square exceeds N. Every unmarked number remaining is prime.
Start: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Cross out multiples of 2 (>2): ✗4 ✗6 ✗8 ✗10 ✗12 ✗14 ✗16 ✗18 ✗20 ✗22 ✗24 ✗26 ✗28 ✗30
Cross out multiples of 3 (>3): ✗9 ✗15 ✗21 ✗27 (others already gone)
Cross out multiples of 5 (>5): ✗25 (others already gone)
√30 ≈ 5.5 - stop here
Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
The sieve is efficient because it never tests the same composite number twice - once it's crossed out, it stays out. For finding a lot of primes at once, it's hard to beat. For testing a single large number, the square root shortcut below is more practical.
The Square Root Trick: Why You Don't Need to Check Everything
To test whether a single number n is prime, you only need to check divisors up to √n. Sounds like a shortcut without a reason behind it, but there's solid logic here. If n has a factor larger than √n, then its paired factor must be smaller than √n - so you'd have already found it. You only need to check up to the square root because anything beyond that point is just the mirror image of a pair you've already tested.
√137 ≈ 11.7 → check primes 2, 3, 5, 7, 11
137 ÷ 2 = 68.5 (not whole)
137 ÷ 3 = 45.67… (not whole)
137 ÷ 5 = 27.4 (not whole)
137 ÷ 7 = 19.57… (not whole)
137 ÷ 11 = 12.45… (not whole)
No divisor found → 137 is prime ✓
√143 ≈ 11.96 → check primes 2, 3, 5, 7, 11
143 ÷ 11 = 13 exactly → 143 = 11 × 13
143 is composite ✗ (a common wrong answer on tests)
You also only need to test prime divisors, not every integer - because any composite divisor would have a prime factor you've already checked. In practice, testing 2, 3, 5, 7, 11, and 13 covers every number up to 14² = 196.
Every Prime from 1 to 100
There are exactly 25 prime numbers between 1 and 100. After 2, they're all odd. After 5, none of them end in 0 or 5.
| 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 |
A few patterns worth noticing: 2 is the only even prime, and 5 is the only one ending in 5. Twin primes - pairs separated by exactly 2 - include (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), and (71, 73). Whether twin primes keep going forever is one of the most famous unsolved problems in mathematics. Nobody knows.
Why Primes Matter for Internet Security
The most widely deployed public-key encryption standard, RSA, depends on a simple and rather beautiful asymmetry: multiplying two large prime numbers together is fast and trivial for any computer, but factoring the result back into those two primes is computationally infeasible at the key sizes used today.
An RSA-2048 key uses two primes each roughly 300 digits long. Their product - the public modulus - is about 600 digits. The best known factoring algorithms would need an estimated millions of years to crack that on modern hardware. That one-way difficulty is what keeps your banking sessions, email, and payment data private.
Two primes: p = 61, q = 53
Public modulus: n = 61 × 53 = 3233
Anyone can see 3233. But working backward to recover 61 and 53
from 3233 alone requires trial and effort - and at 617-digit scale,
that effort exceeds any realistic computational budget.
Primes also show up in hash functions, random number generators, and error-correcting codes. The more math you encounter, the more often they appear - not because mathematicians are obsessed with them, but because their multiplicative irreducibility makes them the atoms from which all other integers are built. Use the CalcSolver Pro prime checker to test any number instantly and see its full prime factorisation.