A prime number can only be divided evenly by 1 and itself. The first 10 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Key Facts
- 2 is the only even prime number
- There are infinitely many primes (proved by Euclid ~300 BC)
- Every integer > 1 can be uniquely factored into primes (Fundamental Theorem of Arithmetic)
Primality Testing
To check if n is prime, test divisibility by all primes up to βn. If none divide evenly, n is prime.