Prime numbers, the indivisible atoms of arithmetic, have captivated mathematicians for over two thousand years. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The Fundamental Theorem of Arithmetic, first stated by Euclid and rigorously proved by Carl Friedrich Gauss, establishes that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. This theorem makes primes the building blocks of all natural numbers, analogous to how chemical elements combine to form all compounds. The sequence of primes begins 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and continues infinitely, as Euclid proved around 300 BCE with an elegant proof by contradiction that remains a model of mathematical reasoning.

The Sieve of Eratosthenes, developed by the Greek mathematician Eratosthenes of Cyrene around 240 BCE, is one of the oldest known algorithms and remains remarkably efficient for finding all primes up to a given limit. The algorithm works by iteratively marking the multiples of each prime number starting from 2. Begin by listing all numbers from 2 to the desired limit. The first unmarked number (2) is prime; mark all its multiples (4, 6, 8, ...) as composite. The next unmarked number (3) is prime; mark all its multiples (6, 9, 12, ...). Continue this process, and all remaining unmarked numbers are prime. An important optimization is that you only need to sieve up to the square root of the limit, since any composite number must have at least one prime factor no larger than its square root. For finding primes up to one million, this algorithm executes in milliseconds on modern hardware.

For testing whether a single large number is prime, more sophisticated algorithms are employed. Trial division, the simplest method, tests whether the number is divisible by any integer from 2 up to its square root. While straightforward, this becomes impractical for very large numbers. The Miller-Rabin primality test, a probabilistic algorithm, works by testing the number against randomly chosen witnesses. If the number passes the test for multiple witnesses, it is almost certainly prime, with the probability of error decreasing exponentially with each additional test. For cryptographic applications where certainty is required, deterministic variants exist that guarantee correctness for numbers below certain bounds. The AKS primality test, published in 2002 by Agrawal, Kayal, and Saxena, was the first algorithm proven to determine primality in polynomial time unconditionally, settling a long-standing theoretical question, though it remains slower in practice than probabilistic methods.

The distribution of prime numbers among the integers follows patterns that continue to intrigue mathematicians. The Prime Number Theorem, proved independently by Jacques Hadamard and Charles-Jean de la Vallee Poussin in 1896, states that the number of primes less than n is approximately n divided by the natural logarithm of n. The Riemann Hypothesis, proposed in 1859 and still unproven, makes a precise conjecture about the distribution of primes that, if true, would provide the tightest known bounds on prime distribution. It remains one of the most important unsolved problems in mathematics, with a one-million-dollar Millennium Prize awaiting its resolution.