Prime Number Checker

Results

1000003 is prime.

Miller–Rabin working

Write n − 1 = 2^s × d with d odd. For each base a, compute a^d mod n and square it up to s − 1 times. n passes the base if a^d ≡ 1, or if some square equals n − 1. Failing even one base proves n is composite.

This is a proof, not a probability. Miller–Rabin with the 2 bases below is deterministic for every number under 1373653.

Neighbouring primes

The gap from the previous prime to the next is 50.

Primes in a range

A segmented sieve of Eratosthenes lists every prime between two numbers, up to 1,000,000,000,000, for ranges of at most 2,000,000 numbers.

How to Use the Prime Number Checker

1. 1. Enter a number. Digits only, with optional spaces between groups. For huge values you can type a power, such as 2^61-1 or 2^16+1, instead of writing out every digit.
2. 2. Read the verdict. Prime and composite are certain. Probable prime appears only above about 3.3 × 10²⁴, where the test is no longer a proof — the page says so.
3. 3. Follow the working. The table shows each Miller–Rabin base, the values it produced and why the number passed or failed. A composite number also gets its prime factors, or its smallest factor if it is too large to factor.
4. 4. Use the neighbours or the range. The previous and next prime appear under the result. For a list, enter two numbers in Primes in a range to get every prime between them, with a count, the largest gap and the twin-prime pairs.

What Makes a Number Prime

A prime is a whole number greater than 1 with exactly two divisors: 1 and itself. Everything else above 1 is composite. The numbers 0 and 1 are neither — 1 is excluded so that every number has exactly one prime factorization. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29, and 2 is the only even one.

Trial division — try every prime up to √n — is the method taught at school, and it is fine up to a few million. It is hopeless for large numbers: a 30-digit number has up to 10¹⁵ candidate divisors to try. That is why the checker uses the Miller–Rabin test instead, and falls back on trial division only for the first 25 primes.

How the Miller–Rabin Test Works

Write n − 1 as 2^s × d with d odd. For a base a, compute a^d mod n and then square the result up to s − 1 times. If n is prime, the sequence must either start at 1 or reach n − 1 (that is, −1) at some point. If it does neither, a is a witness: it proves n is composite. A composite number can occasionally slip past one base, but not past all of a well-chosen set.

The set of bases is chosen from published thresholds (OEIS A014233). Testing the first 4 primes as bases (2, 3, 5, 7) is a proof for every n below 3,215,031,751; the first 12 (2 to 37) prove it below 318,665,857,834,031,151,167,461; and the first 13 (2 to 41) prove it below 3,317,044,064,679,887,385,961,981. The checker uses the smallest list that is proven for your number, and shows it.

Worked Examples

1. 1,000,003 is prime. It has no prime factor up to 97, and n − 1 = 1,000,002 = 2 × 500,001. Below 1,373,653, bases 2 and 3 are a proof, so those two are run — and both give 1,000,002, which is n − 1. It passes both, so it is prime.
2. 12,827 is composite. It has no prime factor up to 97, so trial division does not catch it, but 12,827 − 1 = 2 × 6,413 and 2⁶⁴¹³ mod 12,827 = 1,526, which is neither 1 nor 12,826. Base 2 is a witness. The factors, 101 × 127, are found afterwards.
3. 3,215,031,751 is composite. It is the smallest number that fools bases 2, 3, 5 and 7: all four pass. Base 11 gives 2,129,160,099 and exposes it. Its factors are 151 × 751 × 28,351 — which is why one base is never enough.

Primes in a Range

The range tool uses a segmented sieve of Eratosthenes: it crosses out the multiples of every prime up to √b inside the window from a to b. It handles windows of up to 2,000,000 numbers anywhere below 10¹². There are 25 primes below 100 and 168 below 1,000. In 1 to 100 the largest gap between neighbouring primes is 8, from 89 to 97, and there are 8 twin-prime pairs (primes two apart, such as 11 and 13).

Frequently Asked Questions

Is 1 a prime number?

No. A prime has exactly two divisors and 1 has only one. Excluding it keeps prime factorization unique: if 1 counted, 6 could be written as 2 × 3, 1 × 2 × 3 and so on. 1 is not composite either.

Is 2 the only even prime?

Yes. Every other even number is divisible by 2, so it has at least three divisors: 1, 2 and itself. That is also why the primes after 2 are all odd, and why the next-prime search steps through odd numbers only.

How can I check if a large number is prime?

Use the Miller–Rabin test rather than trial division. This checker applies it with proven bases for numbers below about 3.3 × 10²⁴ and with 20 bases beyond that, in milliseconds, for up to 200 digits.

What does 'probable prime' mean?

The number passed every Miller–Rabin round we ran, but no proof covers its size. Genuine primes always pass; a composite passing 20 prime bases is extraordinarily unlikely, and none is known. For work that needs certainty, such as published results, verify with a primality-proving program.

How do I check whether a number is prime by hand?

Divide it by each prime up to its square root: if none divides it exactly, it is prime. For 391, √391 ≈ 19.8, so test 2, 3, 5, 7, 11, 13, 17 and 19 — and 17 divides it, so 391 = 17 × 23 is composite. Quick shortcuts first: reject even numbers, numbers ending in 5, and numbers whose digits sum to a multiple of 3.

Are there infinitely many primes?

Yes. Euclid proved it around 300 BC: multiply any finite list of primes together and add 1, and the result has a prime factor that is not on the list. Primes thin out slowly — about one number in ln(n) is prime near n — but they never stop.

What is a Mersenne prime?

A prime of the form 2^p − 1, where p is itself prime. 2⁶¹ − 1 = 2,305,843,009,213,693,951 is one; type 2^61-1 to test it. Not every such number is prime: 2¹¹ − 1 = 2,047 = 23 × 89.