Prime number checker and generator

How to use it

The first tab tests a single number: it tells you whether the number is prime, shows the prime factorisation if it is not, counts the divisors, lists them for smaller inputs, and finds the nearest prime on either side. The second tab sieves an interval and lists every prime it contains.

What makes a number prime

A prime is a whole number greater than 1 whose only positive divisors are 1 and itself. 7 is prime; 9 is not, because 3 divides it. Numbers greater than 1 that are not prime are called composite.

1 is deliberately excluded. It has only one positive divisor, and if it counted as prime then unique factorisation would break — 6 could be written as 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3. Mathematicians call 1 a unit instead. Zero and negative numbers are outside the definition entirely.

How the primality test works

A composite number n always has a factor no larger than √n, because if both factors were bigger their product would exceed n. So trial division only has to test primes up to the square root — for 9,973 that means testing up to 99, not up to 9,972.

For large numbers even that is slow, so this tool uses a deterministic Miller–Rabin test. Miller–Rabin asks whether n behaves the way a prime must behave under modular exponentiation for a set of chosen witnesses. With the first twelve primes as witnesses, the test is proven exact for every value below 3.3 × 10²⁴ — it is not a probabilistic guess at that size. Numbers with dozens of digits answer instantly.

Full factorisation is a harder problem than primality testing. This tool factorises by trial division with a 6k ± 1 wheel, which is practical up to about 10¹⁵. Above that it will still tell you whether the number is prime, but not what its factors are — that difficulty gap is precisely what RSA encryption is built on.

Reading the prime factorisation

Every integer above 1 factors into primes in exactly one way, ignoring order. That is the fundamental theorem of arithmetic. The tool writes it in prime-power form, so 360 = 2³ × 3² × 5.

The exponents also give the divisor count without listing anything: multiply each exponent plus one together. For 360 that is (3+1) × (2+1) × (1+1) = 24 divisors, because each prime can appear anywhere from zero times up to its exponent, independently of the others.

The sieve of Eratosthenes

To list every prime in a range, the range generator uses a segmented sieve. It first finds all primes up to √(upper bound) by an ordinary sieve, then walks the requested interval in blocks, crossing off the multiples of each of those base primes. Whatever is left standing is prime. This is far faster than testing each number individually and uses memory proportional to the block size rather than the range.

Alongside the list you get the count, the density, the number of twin-prime pairs (primes two apart, such as 11 and 13) and the largest gap in the interval.

Prime facts worth having

The thinning out is not random: the prime number theorem says the count below n is approximately n ÷ ln(n), which predicts 72,382 below a million — within 8% of the true 78,498. Euclid proved over two thousand years ago that the primes never run out, so there is no largest prime.

Numbers that look prime but are not

• 91 = 7 × 13 — the classic trap, since it survives the divisibility tests for 2, 3 and 5.
• 561 = 3 × 11 × 17 — the smallest Carmichael number, which fools the naive Fermat primality test for every base coprime to it. Miller–Rabin is not fooled.
• 2¹¹ − 1 = 2047 = 23 × 89 — a Mersenne number with a prime exponent that is nonetheless composite.
• 1 — excluded by definition, as above.

Privacy

All the arithmetic, including the big-integer Miller–Rabin test and the sieve, runs inside your browser. Nothing you enter is sent anywhere, which also means the page keeps working offline.