Prime Number Checker

How to use the prime number checker

1. Type a Whole number. Expressions are accepted too: 2^61-1, 10^12+39, 20!+1 or 3711.
2. The answer appears as you type; press Check to give the factorization more time on a hard number.
3. Read the verdict, the Prime factorization, the Number of divisors, the Previous prime and the Next prime. The Why panel explains how the answer was reached, and Copy factorization copies the product of primes.
4. To list primes, fill in From and To under Prime numbers in a range and press List primes.

Numbers up to 2048 bits (about 617 digits) are accepted, and everything runs in your browser.

What makes a number prime

A prime number is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13… A number with other divisors is composite, and it can be written in exactly one way as a product of primes, its prime factorization (360 = 2³ × 3² × 5). The numbers 0 and 1 are neither prime nor composite, and 2 is the only even prime.

The number of divisors follows from the factorization: add 1 to each exponent and multiply. 360 = 2³ × 3² × 5 has (3 + 1)(2 + 1)(1 + 1) = 24 divisors. A prime always has exactly 2.

How the test works

• Small numbers (below one million) are checked by trial division: if no prime up to the square root divides the number, it is prime. There is no need to go further, because a composite number always has a factor no larger than its square root.
• Larger numbers are first divided by every prime below 1000, then put through the Miller–Rabin test. With the 13 bases 2, 3, 5, …, 41, this test has been proven exact for every number below 3.3 × 10²⁴, which includes all 64-bit integers. For those numbers the answer is certain.
• Above 3.3 × 10²⁴, 25 bases are used and a number that passes them all is reported as a probable prime. The chance of error is below 1 in 10¹⁵, but it is not a mathematical proof. When the test fails, the number is certainly composite.

How numbers are factored

Small factors are found by trial division. Larger composite parts are split with Pollard’s rho algorithm (Brent’s variant), which finds factors of up to about 10 digits in a fraction of a second. Harder numbers, such as the product of two primes of 15 digits or more, can take far longer than any time limit, so factoring stops after a few seconds. The last factor is then marked as composite but not split, and pressing Check again gives it more time.

Primes in a range

The range list uses a segmented sieve of Eratosthenes, which crosses out the multiples of each prime. It accepts up to 1,000,000 numbers per range with an upper bound up to 10¹². The count covers the whole range, and the first 2,000 primes are listed. For example, there are 25 primes between 1 and 100 and 78,498 below one million.