Prime number checker
Enter a whole number up to 18,446,744,073,709,551,615 (2^64 − 1). You get a definite answer, the smallest prime factor and full factorization for composite numbers, and the nearest primes below and above.
Runs in your browser: nothing you enter is sent anywhere.
How to use it
- Type a whole number from 0 to 18,446,744,073,709,551,615.
- The result updates as you type: Prime, Composite, or Neither for 0 and 1.
- For a composite number you also see its smallest prime factor and the full factorization, such as 7 × 11 × 13 for 1,001.
- The previous and next primes are shown for every input. “Next” is strictly greater than your number.
How it works
- Small primes (2 to 37) are tried as divisors first.
- The number n − 1 is written as 2^r × d with d odd, and each of the twelve bases is tested with modular exponentiation (Miller–Rabin). One failed base proves the number composite; passing all twelve proves it prime for numbers in this range.
- A composite number is split with trial division or Pollard’s rho, and the parts are checked in turn.
- The neighbours are found by stepping through odd numbers and testing each.
All arithmetic uses exact integers.
Worked example
1,001 is composite: 1,001 = 7 × 11 × 13. The smallest factor is 7, the previous prime is 997 and the next is 1,009.
2^61 − 1 = 2,305,843,009,213,693,951 is prime (a Mersenne prime), and 2^64 − 59 = 18,446,744,073,709,551,557 is the largest prime below 2^64.
Tips
- A quick manual test: a number is divisible by 3 when its digit sum is, by 5 when it ends in 0 or 5, and by 2 when it ends in an even digit.
- To find the divisors of several numbers or their GCD and LCM, use the GCD and LCM calculator.
Frequently asked questions
What is a prime number?
A prime is a whole number greater than 1 whose only divisors are 1 and itself, such as 2, 3, 5, 7 and 11. A number greater than 1 that has other divisors is composite. 0 and 1 are neither.
Is the answer certain or only probable?
It is certain. The test is Miller–Rabin with the first twelve primes as bases (2 to 37), which is proven to give the right answer for every number below 3.3 × 10^24, far above the 2^64 limit here. No random choices are involved.
How are the factors found for large composites?
Numbers up to one trillion are factored by trial division. Larger ones are first divided by the primes below 1,000, then split with Pollard's rho algorithm, with every piece checked for primality. A 64-bit number is factored in a fraction of a second.
Is 1 a prime number?
No. A prime needs exactly two divisors, and 1 has only one. Treating 1 as prime would also break unique factorization, because 6 could be written as 2 × 3, 1 × 2 × 3 and so on.
Is 2 prime? It is even.
Yes, 2 is the only even prime: every other even number is divisible by 2 and therefore composite.