How this calculator works
A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. This calculator runs a deterministic Miller-Rabin test with the first twelve prime bases, which is exact for every value in the accepted range. A candidate that fails any base is certainly composite; a candidate that passes every base is prime. Finding the neighbouring primes repeats the test on nearby integers, and prime gaps are small enough that the search stays quick.
Formula
n is prime when it has exactly two positive divisors. Fermat's little theorem says a^(p-1) ≡ 1 (mod p) for prime p and a not divisible by p; Miller-Rabin tests a related condition and catches every composite that could slip through.
Worked example
97 is prime because no prime up to its square root (about 9.85) divides it: 2, 3, 5 and 7 all leave a remainder. The number 91 = 7 × 13 is composite.
Advertisement
Frequently asked questions
Is 1 a prime number?
No. A prime must be greater than 1 and have exactly two positive divisors. The number 1 has only one divisor, itself, and 0 has infinitely many divisors by some conventions, so neither is prime.
Is 2 the only even prime?
Yes. Every even number greater than 2 is divisible by 2 as well as by 1 and itself, so it is composite. Two is divisible only by 1 and 2.
How is the answer verified?
For this range the Miller-Rabin test with the first twelve prime bases has no known counterexample: its smallest failing composite is far beyond one quadrillion. A composite candidate would also be caught immediately if a small prime divided it.
Why can no prime end in 0, 2, 4, 5, 6 or 8?
Such a number is divisible by 2 or 5, apart from the single-digit primes 2 and 5 themselves. Above 5, every prime ends in 1, 3, 7 or 9, though the reverse is not true: 21 ends in 1 and is composite.