Primality

Primality refers to the property of a natural number greater than 1 being a prime. A prime number has no positive divisors other than 1 and itself. By contrast a composite number has at least one divisor other than 1 and itself. The number 2 is the smallest prime and the only even prime; every even number greater than 2 is composite. The integer 1 is not prime.

Prime numbers are the building blocks of the integers: every integer greater than 1 can be factored uniquely into primes, up to order. This is the Fundamental Theorem of Arithmetic.

Determining whether a given number is prime is called primality testing. A straightforward method is trial division, testing divisibility by integers up to the square root of the number, which is practical only for small values. For sieving primes in a range, the Sieve of Eratosthenes can generate all primes up to N with time roughly O(N log log N) and space O(N).

For very large numbers, probabilistic primality tests are used. The Miller–Rabin test is a common randomized method with controllable error probability; Solovay–Strassen is another probabilistic test. Deterministic variants exist for numbers below certain bounds (for example, specific base sets guarantee correctness for 64-bit integers).

Primality testing is central to number theory and practical applications such as public-key cryptography, where primes are used in key generation and secure protocols. The distribution of primes is still a topic of active research, with questions such as the exact asymptotics of gaps between primes and prime-generating functions being central to analytic number theory.