Maths⏱ 5 min read
What Is a Prime Number and How Do You Find Them?
Prime numbers are the building blocks of all whole numbers. Here's what makes a number prime, the most efficient methods for checking primality, and why primes matter in cryptography.
A prime number is divisible only by 1 and itself. They seem simple — but understanding how to find and verify them efficiently reveals beautiful patterns in mathematics and underpins modern encryption.
The Definition
A prime number has exactly two distinct factors: 1 and itself.
Prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...
Not prime: 1 (has only one factor), 4 (factors: 1, 2, 4),
9 (factors: 1, 3, 9), 15 (factors: 1, 3, 5, 15)
2 is the only even prime — all other even numbers are divisible by 2.
Trial Division: The Basic Method
To check if n is prime:
Test divisibility by all primes up to √n
If n has a factor larger than √n, it must have a corresponding
factor smaller than √n — so checking up to √n is sufficient.
Is 97 prime?
√97 ≈ 9.85, so test primes: 2, 3, 5, 7
97 / 2 = 48.5 (not divisible)
97 / 3 = 32.3 (not divisible)
97 / 5 = 19.4 (not divisible)
97 / 7 = 13.86 (not divisible)
→ 97 is prime ✓
Is 91 prime?
√91 ≈ 9.54, test primes: 2, 3, 5, 7
91 / 7 = 13 exactly
→ 91 = 7 x 13, NOT prime
The Sieve of Eratosthenes
For finding all primes up to a limit, the Sieve is far more efficient than testing each number individually:
Find all primes up to 30:
1. List: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11...30
2. Start with 2 (prime). Cross out all multiples of 2: 4,6,8...
3. Next uncrossed: 3 (prime). Cross out multiples of 3: 9,15,21,27...
4. Next uncrossed: 5 (prime). Cross out multiples of 5: 25...
5. Next uncrossed: 7 (prime). 7x7=49 > 30, so we're done.
Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — all primes to 30
Interesting Prime Patterns
TypeExamples
Twin primes (differ by 2)3&5, 5&7, 11&13, 17&19, 29&31
Mersenne primes (2^n − 1)3, 7, 31, 127, 8191...
Prime triplets(5,7,11), (7,11,13), (11,13,17)
Palindrome primes11, 101, 131, 151, 181, 191
Why Primes Matter for Encryption
RSA encryption — used to secure most internet traffic including banking and email — relies on a fundamental asymmetry: multiplying two large primes together is easy, but factoring the result back into its prime components is computationally infeasible for current computers.
Easy: 104,729 x 224,737 = 23,534,041,073
Hard: Given 23,534,041,073, find its two prime factors.
(The answer is 104,729 and 224,737 — but finding it from
the product alone takes enormous computation for large primes)
In practice: RSA uses primes with 1,024-4,096 binary digits.
Factoring such numbers would take longer than the age of the universe
with current classical computing methods.