Math
Prime number calculator
Enter a whole number to find out whether it is prime, see the divisions that decide it, and get the primes either side. Switch mode to list the primes in a range or to find the nth prime.
Any whole number up to about 3.3 × 10²⁴.
Up to 1,000,000.
Show the working, step by step
A composite number always has a prime factor no bigger than its square root, so only primes up to √221 need testing.
√221 ≈ 14.866 → test primes up to 14
None of these divides 221 exactly:
2, 3, 5, 7, 11
13 divides it:
221 ÷ 13 = 17
So 221 is not prime.
221 = 13 × 17
Nearest primes, found by testing each number in turn:
previous 211, next 223
How a number is tested
n is prime ⇔ n > 1 and no prime p ≤ √n divides n
For numbers up to 10¹² the calculator uses trial division: it divides by each prime up to the square root and stops at the first one that goes in exactly. That is the method you would use by hand, and the working lists every prime it tried. Bigger numbers go through a deterministic Miller–Rabin test, explained in the FAQ.
A worked example: is 221 prime?
- √221 ≈ 14.87, so only the primes 2, 3, 5, 7, 11 and 13 need testing.
- 221 is odd, its digit sum 5 is not a multiple of 3, and it does not end in 0 or 5.
- 221 ÷ 7 = 31.57… and 221 ÷ 11 = 20.09…, neither exact.
- 221 ÷ 13 = 17 exactly.
So 221 = 13 × 17 is not prime. It is a good example of a number that looks prime: it passes every quick divisibility rule. The nearest primes are 211 below and 223 above.
The sieve of Eratosthenes
To list all primes in a range, it is faster to cross out composites than to test each number. Write out the numbers, then cross out the multiples of 2, then of 3, then of 5, and so on for every prime up to the square root of the largest number. Whatever is left is prime. From 1 to 100 that leaves 25 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
Primes to know
| Range | Number of primes |
|---|---|
| Below 10 | 4 |
| Below 100 | 25 |
| Below 1,000 | 168 |
| Below 10,000 | 1,229 |
| Below 1,000,000 | 78,498 |
Common misconceptions
- “All odd numbers are prime.” 9, 15, 21 and 221 are odd and composite.
- “2 is not prime because it is even.” 2 is prime; it is the only even prime.
- “Numbers ending in 1, 3, 7 or 9 are prime.” That only rules out factors of 2 and 5. 91 = 7 × 13.
- Fermat’s test is enough. Carmichael numbers such as 561 = 3 × 11 × 17 fool it for every base coprime to them; Miller–Rabin does not have this weakness.
Common questions
What is a prime number?
A whole number greater than 1 whose only divisors are 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. A number greater than 1 that is not prime is composite: it can be written as a product of smaller whole numbers, as 221 = 13 × 17.
Is 1 a prime number?
No. A prime has exactly two different divisors, and 1 has only one. Leaving 1 out also keeps prime factorisation unique: if 1 were prime, 6 could be written as 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on.
Why only test divisors up to the square root?
If n = a × b and both a and b were bigger than √n, their product would be bigger than n. So any composite number has a factor no larger than its square root. For 221, √221 ≈ 14.87, so testing 2, 3, 5, 7, 11 and 13 is enough; 13 divides it.
How does the calculator test very large numbers?
Above 10¹² it uses the Miller–Rabin test with the first twelve primes (2 to 37) as bases. For any number below about 3.3 × 10²⁴ that set of bases is proven to give the right answer every time, so the result is certain rather than probable. It takes a fraction of a second even for a 25-digit number.
How many primes are there?
Infinitely many, as Euclid proved: multiply any finite list of primes together and add 1, and the result has a prime factor not on the list. They thin out slowly: 25 primes below 100, 168 below 1,000, and 78,498 below 1,000,000. The prime number theorem says there are roughly x ÷ ln x primes below x.
What is the millionth prime?
15,485,863. The 100th prime is 541 and the 10,000th is 104,729. Choose “Find the nth prime” above for any n up to one million.
Related calculators
-
Prime factorisation
Split a composite number into its primes.
-
Divisibility rules
Quick digit tests for small divisors.
-
Number theory toolbox
Totient, divisor sums and more.
-
GCD and LCM
Common factors and multiples.