Home › Math & Science › Prime Number Checker

Prime Number Checker

Use this free prime number checker to test whether any whole number up to 10^18 is prime. Type a number and it gives a clear verdict — prime or composite — and, for composite numbers, the smallest divisor it found. You can also find the next prime or the previous prime after any number, and list every prime inside a range. It runs entirely in your browser, with no sign-up and nothing to install.

How it works

A prime number is a whole number greater than 1 that can only be divided evenly by 1 and itself: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and so on. The number 2 is the only even prime — every other even number is divisible by 2, so it cannot be prime. Every whole number greater than 1 that is not prime is composite, meaning it can be built by multiplying primes together: 91, for example, is 7 × 13. Primes are the atoms of arithmetic, and this checker tells you, for any number you type, which of the two kinds it is.

For numbers up to 1,000,000 the checker uses trial division, the oldest and most reliable method. It tries dividing the number by every prime up to its square root — 2, 3, 5, 7, 11 and so on. It only needs to go that far, because any factor larger than the square root has a partner factor smaller than it that would already have been found. If none of those primes divides the number evenly, the number is prime. When a divisor is found, the checker reports the smallest one, so for 91 it reports 7 rather than 13.

For larger numbers, trial division would be far too slow — the square root of a trillion is a million, and the square root of 10^18 is a billion. So the checker switches to the Miller-Rabin test, which raises numbers to powers and checks the remainders. It tests the number against twelve fixed bases: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37. Mathematicians have proved those bases make the test exact for every number below about 3.3 × 10^24, which covers the whole 10^18 range this checker accepts. The verdict is certain, not a probability, and it arrives in a fraction of a second.

The other three modes build on the same test. "Next prime" steps upward from your number, testing each odd number in turn until it finds a prime — the next prime after 100 is 101, and after 1,000 it is 1,009. "Previous prime" steps downward the same way; there is no prime below 2, so the checker says so plainly if you ask for the previous prime of 2. "List primes" runs a sieve of Eratosthenes over your range: it marks off the multiples of each prime in turn, and whatever is left unmarked is prime. The sieve is the fastest way to list many primes at once, which is why it is used here instead of testing each number one by one.

The number line beside the calculator shows the same idea as a picture. It draws the integers around your number and marks the primes in blue, so you can see how primes thin out as numbers grow — 25 primes below 100, but only 168 below 1,000, and the gaps between them slowly widen. Your number is ringed, so you can see where it sits among its neighbours.

Two special cases deserve an honest answer instead of a made-up one. The number 1 is neither prime nor composite: it has only one factor, itself, and a prime needs exactly two factors. Zero is not prime either, because it can be divided evenly by every number — 0 divided by 7 is 0, with nothing left over. Negative numbers are not accepted, because primality is defined for positive whole numbers. The checker shows a friendly message for each of these cases instead of a wrong or empty result.

Prime numbers matter far beyond homework. They are the building blocks of every whole number, they make the greatest common factor and least common multiple easy to find, and they sit at the heart of modern cryptography: the encryption that protects online banking rests on multiplying two large primes being easy while working out which primes were used is enormously hard. Checking primality is the first step in finding large primes for that work, which is why a fast, exact test matters.

Worked example

Check 97 by hand, the way the calculator does it. Its square root is about 9.8, so only the primes 2, 3, 5 and 7 need testing. 97 is odd, so 2 does not divide it. Its digits add to 9 + 7 = 16, which is not divisible by 3, so 3 does not divide it. It does not end in 0 or 5, so 5 does not divide it. And 7 × 13 = 91 and 7 × 14 = 98, so 7 does not divide it either. None of the primes up to the square root divides 97, so the verdict is prime. Type 97 into the checker and it gives the identical result: 97 is prime.

Now try 91. Its square root is about 9.5, so the same primes are tested. 2, 3 and 5 fail as before, but 7 divides 91 exactly: 91 ÷ 7 = 13. The checker reports 91 as composite with smallest divisor 7, and the full split 91 = 7 × 13. The number line shows 89 and 97 in blue on either side, with 91 sitting between them unmarked.

For the other modes, try 100 in "Next prime" mode. The checker tests 101 first — 101 is odd, not divisible by 3 (1 + 0 + 1 = 2), 5 or 7 (7 × 14 = 98, 7 × 15 = 105) — and its square root is just over 10, so only 2, 3, 5 and 7 need testing. The answer is 101. In "List primes" mode, the range 1 to 30 gives exactly 10 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

FAQ