🔑 Prime Calculators

What Makes a Number Prime?

A prime number is a natural number greater than 1 that has exactly two divisors: 1 and itself. The number 2 is the only even prime; every other even number is divisible by 2 and therefore composite. The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The number 1 is not prime by definition — if it were, unique factorisation would break down (e.g., 6 = 2×3 = 2×3×1 = 2×3×1×1 ...). There are infinitely many primes, proven by Euclid around 300 BCE: assume there are finitely many primes p₁, p₂, ..., pₙ; consider N = (p₁×p₂×...×pₙ) + 1; N is not divisible by any of the listed primes, so it is either prime itself or has a prime factor not on the list — contradiction.

Primality Testing Algorithms

The simplest primality test — trial division — checks whether n is divisible by any integer from 2 to √n. If no divisor is found, n is prime. This is sufficient for numbers up to a few million. The Sieve of Eratosthenes generates all primes up to N in O(N log log N) time by iteratively marking multiples of each prime. For large numbers, the Miller-Rabin probabilistic test is efficient: it identifies composites with very high probability using modular exponentiation and can be made deterministic for numbers up to practical limits by choosing specific test bases. The AKS primality test (2002) runs in polynomial time and is always correct, though it is slower than Miller-Rabin in practice.

Prime Factorization and the Fundamental Theorem

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of primes in exactly one way (ignoring order). For example, 360 = 2³ × 3² × 5. Prime factorization is the foundation of number theory and has direct applications in cryptography. RSA encryption relies on the fact that multiplying two large primes together is easy, but factoring the product back into its prime components is computationally infeasible for primes with hundreds of digits. Prime factorization also determines the GCD and LCM of two numbers: GCD = product of common prime factors with minimum exponents; LCM = product of all prime factors with maximum exponents.

Twin Primes and Special Prime Sequences

Twin primes are pairs of primes that differ by exactly 2, such as (3,5), (11,13), (17,19), (29,31), and (41,43). The Twin Prime Conjecture, unproven since antiquity, states there are infinitely many such pairs. Cousin primes differ by 4; sexy primes differ by 6. Sophie Germain primes are primes p where 2p+1 is also prime, important in cryptography. Mersenne primes have the form 2ⁿ−1 (e.g., 3, 7, 31, 127); they are used in large prime searches and some random number generators. The Great Internet Mersenne Prime Search (GIMPS) has found the largest known primes — as of 2024, the largest known prime is 2¹³⁶²⁷⁹⁸⁴¹ − 1 with over 41 million digits.