A prime number is a whole number greater than 1 that has exactly two factors: 1 and itself. Prime numbers are the building blocks of all integers — every whole number can be expressed as a product of primes.
The First 25 Prime Numbers
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
Note that 2 is the only even prime number. All other even numbers are divisible by 2.
Method 1: Trial Division
The simplest way to test if a number is prime — check if any number up to its square root divides it evenly.
Key insight: If n has a factor greater than √n, it also has a corresponding factor less than √n. So you only need to check up to √n.
Algorithm:
- If n < 2, not prime
- If n = 2, prime
- If n is even (except 2), not prime
- Check all odd numbers from 3 to √n
- If any divide n evenly, not prime
- Otherwise, prime
Example: Is 97 prime?
√97 ≈ 9.85, so check primes up to 9: 2, 3, 5, 7
- 97 ÷ 2 = 48.5 (not whole)
- 97 ÷ 3 = 32.33... (not whole)
- 97 ÷ 5 = 19.4 (not whole)
- 97 ÷ 7 = 13.86 (not whole)
No divisors found — 97 is prime.
Example: Is 91 prime?
√91 ≈ 9.54, check up to 9: 2, 3, 5, 7
- 91 ÷ 7 = 13 (whole number!)
91 is not prime — 91 = 7 × 13.
Method 2: Sieve of Eratosthenes
The Sieve of Eratosthenes finds all primes up to a given limit. It's fast and elegant, invented by the Greek mathematician Eratosthenes around 240 BC.
To find all primes up to 50:
- Write out numbers 2 to 50
- Start with 2 (first prime). Cross out all multiples of 2 (4, 6, 8...)
- Move to the next uncrossed number: 3. Cross out multiples of 3 (9, 15, 21...)
- Next uncrossed: 5. Cross out multiples of 5 (25, 35...)
- Next uncrossed: 7. Cross out multiples of 7 (49...)
- Stop when you reach √50 ≈ 7.07
- All remaining uncrossed numbers are prime
Primes up to 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Primes up to 100: Complete List
| Range | Primes |
|---|---|
| 1–10 | 2, 3, 5, 7 |
| 11–20 | 11, 13, 17, 19 |
| 21–30 | 23, 29 |
| 31–40 | 31, 37 |
| 41–50 | 41, 43, 47 |
| 51–60 | 53, 59 |
| 61–70 | 61, 67 |
| 71–80 | 71, 73, 79 |
| 81–90 | 83, 89 |
| 91–100 | 97 |
There are 25 primes below 100.
Quick Divisibility Tests
Before doing full division, check these rules:
| Divisible by | If... |
|---|---|
| 2 | Last digit is even (0,2,4,6,8) |
| 3 | Sum of digits divisible by 3 |
| 5 | Last digit is 0 or 5 |
| 7 | No simple rule — just divide |
| 11 | Alternating digit sum divisible by 11 |
Example: Is 143 prime?
- Not even ✓
- 1+4+3 = 8, not divisible by 3 ✓
- Doesn't end in 0 or 5 ✓
- √143 ≈ 11.96, check up to 11
- 143 ÷ 7 = 20.43 ✓
- 143 ÷ 11 = 13 — divisible!
143 = 11 × 13. Not prime.
Why Primes Matter
Cryptography: RSA encryption — used to secure internet banking, HTTPS, and email — relies on the fact that multiplying two large primes is easy, but factoring the result back into primes is extremely hard.
Computer science: Hash tables, random number generators, and checksums use properties of prime numbers.
Pure mathematics: The distribution of primes remains one of the deepest unsolved problems in mathematics — the Riemann Hypothesis.
Interesting Prime Facts
- The largest known prime (as of 2024) has over 41 million digits
- Twin primes are primes that differ by 2 (11 and 13, 17 and 19, 41 and 43)
- There are infinitely many primes — proven by Euclid around 300 BC
- Goldbach's conjecture (unproven since 1742): every even number > 2 is the sum of two primes