Is your number a prime number?

How it works

A prime number is a whole number above 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11 and so on. Every other number above 1 is composite and is a product of primes in exactly one way, apart from the order: 1200 = 2⁴ × 3 × 5². The numbers 0 and 1 are neither prime nor composite.

Dividing by every possible factor is far too slow for big numbers, so the check uses the Miller–Rabin test. It takes a base a and looks for a pattern in the powers of a that every prime must follow; a composite number usually breaks the pattern, and the base that breaks it is a witness. Below about 3.3 × 10²⁴ a fixed set of the first 13 primes as bases is known to catch every composite, so “prime” there is a proof. Above that, no fixed set is proven, so a number that passes 20 bases is shown as “probably prime”: certain enough for practice, but not a proof. “Not prime” is always a proof.

Prime factors are found by trial division, which is instant up to 10¹⁵ (a thousand trillion). Above that a composite number is recognised as composite but not factored here. That gap is no accident: testing whether a number is prime is much easier than finding its factors, and much of modern encryption relies on it.