Definition
A prime number is a natural number greater than 1 with no positive divisors other than 1 and itself. The first few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23. By the fundamental theorem of arithmetic, every integer greater than 1 has a unique factorization into primes.
Why it matters
How it works
To test whether n is prime, the simplest method is trial division: check whether any integer from 2 to √n divides n. If none does, n is prime. This is O(√n) and works for practical sizes; for very large numbers, probabilistic tests (Miller-Rabin) and deterministic polynomial-time tests (AKS) are used. The set of primes is decidable but has no simple generating formula; primes are "discovered," not "generated" in the way composites are.