Prime Number Checker

A prime number is a whole number greater than 1 that has no divisors other than 1 and itself, which is another way of saying it has exactly two divisors. The run starts 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and everything else above 1 is composite: 4 is 2×2, 6 is 2×3, and 8, 9 and 10 all break down further. The number 1 is not prime by definition, and 2 is the only even prime, because every other even number divides by 2. Gaps between consecutive primes widen on average but do so irregularly, which is why twin pairs such as 11 and 13, 17 and 19, or 29 and 31 keep turning up.

This calculator checks whether a given number is prime by testing divisibility up to its square root, which is enough, because any larger factor would already have been caught paired with a smaller one. It also produces the complete prime factorisation of composite numbers, lists every prime within a range such as 1 to 1,000, and finds the next prime above or below a number you enter. Factorisation is the workhorse behind simplifying fractions and behind finding the lowest common multiple or greatest common divisor of two numbers.

Primes are the building blocks of the integers. The Fundamental Theorem of Arithmetic says that every integer above 1 has a unique prime factorisation, so the factor list works as a fingerprint. That uniqueness, combined with the difficulty of reversing it, is what modern internet security rests on. RSA encryption multiplies two large primes together and depends on nobody being able to factor the result, a semiprime, in reasonable time. RSA-2048, the current standard, uses 617-digit primes. The same properties turn up in error-correcting codes, random number generation and hash functions.

Several methods exist for deciding primality, and they suit different sizes of number. Trial division checks whether N divides by anything from 2 up to √N, which is fine for small numbers and hopeless for large ones. The Sieve of Eratosthenes is the efficient route to every prime up to N, working by striking out multiples. Miller-Rabin is probabilistic, very fast on large numbers, and returns a high-confidence answer rather than a certain one. The AKS test, published in 2002, is deterministic and runs in polynomial time, which made it theoretically important, although it remains slower in practice than Miller-Rabin.

Big primes attract record-hunters. The largest known prime as of 2024 is 2^136,279,841 − 1, a Mersenne prime with 41 million digits, found through the Great Internet Mersenne Prime Search using distributed computing. Several simple-sounding questions about primes are still open. The twin primes conjecture asks whether pairs of that kind go on forever, and is believed true but unproven. Goldbach's conjecture, that every even number above 2 is the sum of two primes, has been verified to 4 × 10^18 without being proved. The Riemann hypothesis, which concerns how primes are distributed, carries an unclaimed $1M Millennium Prize.

For UK students the subject runs from school arithmetic into serious number theory. A-level Maths covers the Fundamental Theorem, highest common factor and lowest common multiple, the Euclidean algorithm for finding a GCD, modular arithmetic and Fermat's Little Theorem, which states that a^p ≡ a mod p for prime p, along with the basics of public-key cryptography. Undergraduate courses go further into Diophantine equations, congruences and quadratic residues, and the cryptography pathways at Bristol, Royal Holloway and Birmingham build directly on that material.