Prime numbers explained
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. A whole number greater than 1 that is not prime is called composite, because it is made by multiplying smaller numbers together. The numbers 0 and 1 are neither prime nor composite.
Every composite number can be written as a product of primes in exactly one way, apart from the order. This is the fundamental theorem of arithmetic, and it is why primes are called the building blocks of the whole numbers. For example, 60 = 2² × 3 × 5 and 91 = 7 × 13.
How this checker works
- Small divisors first. The number is divided by every prime up to 10,000. This instantly settles most inputs and finds their small factors.
- Miller–Rabin test. Larger candidates are checked with the Miller–Rabin test using the first 13 primes as bases. For any number below about 3.3 × 10²⁴ this combination is proven to give the right answer, so every result up to that size, including everything up to JavaScript's largest safe integer (9,007,199,254,740,991), is exact.
- Bigger numbers. Above 3.3 × 10²⁴ the result is shown as "probably prime". No composite number is known to pass all 13 rounds, but the test is not a proof at that size. The checker accepts up to 100 digits and uses exact big-integer arithmetic throughout.
- Factorization. Factors beyond the trial-division range are found with Pollard's rho algorithm. Numbers made of two very large primes, like the ones used in RSA keys, cannot be factored in a browser, and the checker says so.
Checking by hand
To test a small number yourself, you only need to try dividing by primes up to its square root. If n = a × b and both a and b were larger than √n, their product would be larger than n. So to check 97, try 2, 3, 5 and 7 (since √97 ≈ 9.8). None divides evenly, so 97 is prime. For 91, 7 divides it exactly, giving 13, so 91 is composite even though it looks prime.
Interesting primes and near misses
- Twin primes are pairs that differ by 2, such as 11 and 13 or 101 and 103.
- Mersenne primes have the form 2ᵖ − 1. 2³¹ − 1 = 2,147,483,647 is one, and the largest known primes are all Mersenne primes.
- Carmichael numbers such as 561 = 3 × 11 × 17 fool the simpler Fermat primality test, which is why Miller–Rabin is used instead.
Why primes matter
Public-key cryptography such as RSA relies on the fact that multiplying two large primes is easy but splitting the product back into those primes is extremely hard. Primes also turn up in hash table sizes, random number generators and error-correcting codes.
