Home / Math / Prime Number Checker
Prime Number Checker
Type a whole number of up to 19 digits to find out whether it is prime. If it is composite you get its smallest prime factor, and either way the nearest primes on each side.
What counts as prime
A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. The first few are 2, 3, 5, 7, 11, 13 and 17. A whole number greater than 1 that is not prime is called composite, because it can be built by multiplying smaller whole numbers. Zero and one are neither: one has just a single divisor, and zero is divisible by everything.
The number 2 is the only even prime. Every other even number has 2 as a second divisor, so testing for evenness removes half of all candidates immediately.
How the test works
For small inputs trial division would be enough, but checking every divisor up to the square root of a 19-digit number would take billions of steps. This page instead uses the Miller-Rabin test. It writes n − 1 = 2s × d with d odd, then examines the sequence ad, a2d, a4d … modulo n for a chosen base a. A prime always produces either 1 at the start or n − 1 somewhere in that chain. A composite number usually fails for most bases.
Some composites pass for a particular base, and they are called strong pseudoprimes to that base. The number 25,326,001 passes for bases 2, 3 and 5, for example. Using the first twelve primes as bases makes the result a proof rather than a probability for every number below about 3.18 × 1023 (a bound published by Sorenson and Webster in 2015), which is well beyond the 19 digits accepted here.
Reading the result
- Smallest prime factor: for a composite number the page divides by 2 and then by odd numbers up to one million. If a factor turns up, it is the smallest prime factor, and the cofactor is the number divided by it.
- Above 1,000,000: the number is certainly composite, but its factors are all large. Finding them is the hard problem of factoring, which this page does not attempt. For numbers up to a trillion use the prime factorization calculator.
- Previous and next prime: found by testing the neighbouring numbers one at a time. Gaps between primes grow slowly, so the search stays short.
Common mistakes and limits
Do not trust divisibility shortcuts alone. A number that survives the rules for 2, 3 and 5 can still be composite, as 49 and 91 show. The number 91 looks prime to many people, yet it equals 7 × 13. Carmichael numbers such as 561 pass the simple Fermat test for every base coprime to them, which is one reason stronger tests exist.
Input must be digits only; negative numbers, decimals and scientific notation are rejected. Commas and spaces are stripped so that you can paste a number written as 1,000,000,007. Primality here concerns the whole number you enter, not its digits or any property of its decimal form.
Worked example
Test 1,000,000,007, a well-known prime just above one billion that programmers often use as a modulus.
Inputs
| Number to test | 1000000007 |
|---|
Result
It has exactly two divisors: 1 and itself.
| Digits | 10 |
|---|---|
| Previous prime | 999999937 |
| Next prime | 1000000009 |
| Method | Trial division by 12 small primes, then Miller-Rabin with the first 12 primes as bases |
Accuracy note: Results use standard double-precision arithmetic, so very large or very small values may be rounded. Check important results by another method.
Frequently asked questions
How do I check if a number is prime?
Test whether any prime up to its square root divides it. For small numbers that is quick by hand, and for large numbers this page applies the Miller-Rabin test instead.
Is 1 a prime number?
No. A prime must have exactly two different positive divisors, and 1 has only one. Modern mathematics also excludes it so that factorization into primes stays unique.
Is the result a proof or only a probability?
For every number this page accepts, the twelve fixed bases give a deterministic answer, so the verdict is a proof. Random-base versions of Miller-Rabin give only a high probability.
Why is 2 the only even prime?
Any larger even number is divisible by 2 as well as by 1 and itself, so it has at least three divisors and cannot be prime.
How many digits can I test?
You can enter up to 19 digits. The page computes with exact big integers, so there is no rounding in the arithmetic even at that size.
Related calculators
References and sources
- Miller, G. L. (1976), Riemann's hypothesis and tests for primality, Journal of Computer and System Sciences.
- Rabin, M. O. (1980), Probabilistic algorithm for testing primality, Journal of Number Theory.
- Sorenson, J. and Webster, J. (2015), Strong pseudoprimes to twelve prime bases, Mathematics of Computation.