Prime Number Checker
Type any whole number, even a 60-digit one, to find out if it is prime, see its prime factorization, factor tree and divisors, or list every prime in a range.
All divisors
Factor tree
Range size up to 10,000,000 numbers, end up to 10¹⁴. Uses a segmented Sieve of Eratosthenes.
How to use the Prime Number Checker
- Type a number or an expression such as 2^31-1, or tap one of the examples.
- Press Check prime to see whether it is prime and why, with the working shown.
- Read the factorization, divisors and factor tree for composite numbers, and download the tree as SVG.
- Switch to Primes in a range, enter a start and end, and press Find primes.
- Copy or download the complete list of primes.
How the primality test works
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. For small numbers the checker uses trial division: if no prime up to √n divides n, then n is prime. For example, √97 ≈ 9.8 and none of 2, 3, 5 or 7 divides 97, so 97 is prime.
For large numbers it uses the Miller–Rabin test with exact big-integer arithmetic. Write n − 1 = 2ˢ × d with d odd; for each base a, n passes if ad ≡ 1 (mod n) or a2ʳd ≡ −1 (mod n) for some r < s. Testing the 13 prime bases 2 to 41 is proven to be deterministic for every n below 3.3 × 10²⁴. Above that, 25 bases are used and the result is reported as a strong probable prime (the chance of error is astronomically small).
Prime factorization and factor trees
Every whole number greater than 1 can be written as a product of primes in exactly one way (the fundamental theorem of arithmetic). The tool divides out small primes first, then splits large composite parts with Pollard's rho (Brent's variant), which finds factors of 20-digit numbers in milliseconds. Example: 360 = 2 × 180 = 2 × 2 × 90 = … = 2³ × 3² × 5.
From the factorization n = p₁a × p₂b × …, the number of divisors is (a + 1)(b + 1)…, so 360 has 4 × 3 × 2 = 24 divisors. Euler's totient φ(n) counts the numbers up to n that share no factor with n.
How many primes are there?
| Up to | Number of primes π(n) | Largest prime below |
|---|---|---|
| 10 | 4 | 7 |
| 100 | 25 | 97 |
| 1,000 | 168 | 997 |
| 10,000 | 1,229 | 9,973 |
| 100,000 | 9,592 | 99,991 |
| 1,000,000 | 78,498 | 999,983 |
| 10,000,000 | 664,579 | 9,999,991 |
The prime number theorem says π(n) is roughly n ÷ ln(n), so primes thin out slowly but never stop: Euclid proved there are infinitely many. The range finder uses a segmented Sieve of Eratosthenes, crossing out multiples of each prime up to √(end).
Special kinds of numbers
- Twin primes differ by 2, like 11 and 13 or 101 and 103.
- Mersenne primes have the form 2ᵖ − 1, such as 2⁶¹ − 1 = 2,305,843,009,213,693,951.
- Carmichael numbers such as 561 = 3 × 11 × 17 pass the simple Fermat test for every base coprime to them, which is why Miller–Rabin is used instead.
- Semiprimes are products of two primes – the basis of RSA encryption.
Frequently asked questions
How do I know if a number is prime?
Check whether any prime up to its square root divides it evenly. If none does, it is prime. For example, 91 is not prime because 7 × 13 = 91, but 89 is prime because none of 2, 3, 5 or 7 divides it.
Is 1 a prime number?
No. A prime must have exactly two different divisors, 1 and itself. The number 1 has only one divisor, so it is neither prime nor composite. The smallest prime is 2, the only even prime.
How large a number can I check?
Up to 60 digits. Numbers below 3.3 × 10²⁴ are proven prime or composite exactly; larger ones use extra Miller–Rabin rounds and are reported as strong probable primes. Factoring very large numbers with two big prime factors may take longer than the browser allows.
What is a factor tree?
A diagram that splits a number into two factors, then splits each composite factor again, until only primes remain at the leaves. Multiplying the green prime leaves gives back the original number.
What is the Miller–Rabin test?
A fast primality test based on modular exponentiation. Each base either proves a number composite or lets it pass. With the right set of bases it is deterministic for all numbers below a known bound.
Is my number sent anywhere?
No. All calculations run in your browser with JavaScript BigInt; nothing is uploaded.