Prime Numbers
A prime number is a number greater than 1 that has no divisors other than 1 and itself. Primes are the fundamental building blocks of all integers.
The Sieve of Eratosthenes
This ancient algorithm, created over 2,000 years ago, efficiently finds all primes up to a given number. Watch as composites get crossed out:
Why Primes Matter for Cryptography
Easy: Multiplication
Given two large primes, multiplying them is fast:
61 × 53 = 3233
(instant computation)
Hard: Factoring
Given the product, finding the primes is hard:
3233 = ? × ?
(must try many divisors)
RSA encryption relies on this asymmetry. The public key contains a large number that is the product of two secret primes. Breaking the encryption requires factoring that number, which is computationally infeasible for large enough primes.
Prime Checker
Check if a number is prime:
Prime Factorization
See how any number can be broken down into prime factors:
How Many Primes Are There?
There are infinitely many primes! Euclid proved this around 300 BCE. The proof is elegant:
Euclid's Proof
- Assume there are only finitely many primes: p₁, p₂, ..., pₙ
- Consider N = (p₁ × p₂ × ... × pₙ) + 1
- N is not divisible by any of our primes (it leaves remainder 1)
- So N is either prime itself, or divisible by a prime not in our list
- Contradiction! There must be infinitely many primes.
The Prime Number Theorem
While primes become rarer as numbers get larger, we know approximately how many primes there are below any given number:
Where π(n) counts primes less than or equal to n. This means roughly 1 in every ln(n) numbers near n is prime.