Enter a number to check if it is prime, or switch to List mode to list all primes up to N.
Prime Numbers Properties & Significance
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. 97 is prime; 91 is not, because 91 = 7 × 13. To check a number by hand, try dividing it by each prime up to its square root. The calculator above does this instantly for numbers up to 1018 and also shows the prime factorization, the divisors and the nearest primes.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23... 2 is the only even prime. There are infinitely many primes, proved by Euclid around 300 BC.
By the Fundamental Theorem of Arithmetic, every integer greater than 1 is either prime or can be expressed uniquely as a product of primes. This makes primes the fundamental building blocks of all integers.
How to Check if Prime
Sieve of Eratosthenes
Prime Factorization
Primes in Cryptography
All 25 Primes Up to 100
| Range | Primes | Count |
|---|---|---|
| 1 to 10 | 2, 3, 5, 7 | 4 |
| 11 to 20 | 11, 13, 17, 19 | 4 |
| 21 to 30 | 23, 29 | 2 |
| 31 to 40 | 31, 37 | 2 |
| 41 to 50 | 41, 43, 47 | 3 |
| 51 to 60 | 53, 59 | 2 |
| 61 to 70 | 61, 67 | 2 |
| 71 to 80 | 71, 73, 79 | 3 |
| 81 to 90 | 83, 89 | 2 |
| 91 to 100 | 97 | 1 |
How Many Primes Are There?
Primes thin out as numbers grow, but slowly. The prime number theorem says the count up to n is roughly n divided by the natural log of n. From 100 upward the true count runs about 8% to 16% above that estimate.
| Up to | Number of primes | Estimate n ÷ ln n | Largest prime below |
|---|---|---|---|
| 10 | 4 | 4 | 7 |
| 100 | 25 | 22 | 97 |
| 1,000 | 168 | 145 | 997 |
| 10,000 | 1,229 | 1,086 | 9,973 |
| 100,000 | 9,592 | 8,686 | 99,991 |
| 1,000,000 | 78,498 | 72,382 | 999,983 |
So about 1 in 4 numbers below 100 is prime, but only about 1 in 13 below a million. The List mode above runs the Sieve of Eratosthenes up to 100,000 and shows the same counts.
Numbers That Look Prime but Are Not
Odd numbers that do not end in 5 are easy to mistake for primes. These come up often in quizzes and fraction problems:
| Number | Factors | Number | Factors |
|---|---|---|---|
| 51 | 3 × 17 | 143 | 11 × 13 |
| 57 | 3 × 19 | 161 | 7 × 23 |
| 87 | 3 × 29 | 169 | 13² |
| 91 | 7 × 13 | 187 | 11 × 17 |
| 119 | 7 × 17 | 221 | 13 × 17 |
| 133 | 7 × 19 | 1,001 | 7 × 11 × 13 |
Quick checks before you divide
- By 3: add the digits. 51 gives 5 + 1 = 6 and 87 gives 8 + 7 = 15, both multiples of 3, so neither number is prime.
- By 11: alternate adding and subtracting the digits. For 187 that is 1 − 8 + 7 = 0, so 11 divides it.
- Stop at the square root. For 221, the square root is about 14.9, so only 2, 3, 5, 7, 11 and 13 need testing. 13 works: 221 = 13 × 17.
- Remember the special cases. 2 is prime (the only even one), 1 is not prime, and 0 and negative numbers are never prime.
How the Calculator Checks Big Numbers
Trial division is fine for small numbers, but an 18-digit number would need about a billion divisions. The calculator uses the Miller-Rabin test with the twelve prime bases from 2 to 37, which is proven to give no wrong answers for any number below 264 (about 1.8 × 1019). It never trusts the simpler Fermat test, which is fooled by Carmichael numbers such as 561 = 3 × 11 × 17. Composite numbers are split with Pollard's rho method, so even a product of two 9-digit primes factors in a fraction of a second. For factors shared between numbers, try the GCF calculator or the LCM calculator.