Prime Number Checker
Check whether a number is prime, up to 100 digits. Composite numbers get their full prime factorization, and every number gets its nearest primes on either side.
Prime: a whole number above 1 whose only divisors are 1 and itself
The 25 Primes Below 100
Worth memorising: any number below 10,000 that isn't divisible by one of these is prime, since √10,000 = 100.
| Range | Primes |
|---|---|
| 1–10 | 2, 3, 5, 7 |
| 11–20 | 11, 13, 17, 19 |
| 21–30 | 23, 29 |
| 31–40 | 31, 37 |
| 41–50 | 41, 43, 47 |
| 51–60 | 53, 59 |
| 61–70 | 61, 67 |
| 71–80 | 71, 73, 79 |
| 81–90 | 83, 89 |
| 91–100 | 97 |
Divisibility Tests to Try First
These rules rule out most composite numbers in seconds. Between them, 2, 3 and 5 alone divide about 73% of all whole numbers.
| Divisor | Test | Example |
|---|---|---|
| 2 | Last digit is even | 1,358 → 8 |
| 3 | Digit sum divisible by 3 | 471 → 4+7+1 = 12 |
| 5 | Ends in 0 or 5 | 2,345 |
| 7 | Double the last digit, subtract from the rest; repeat | 203 → 20 − 6 = 14 |
| 11 | Alternating digit sum divisible by 11 | 2,728 → 2−7+2−8 = −11 |
| 13 | Add 4 × last digit to the rest; repeat | 221 → 22 + 4 = 26 |
Worked Example: Is 391 Prime?
391 is odd, doesn't end in 5, and its digits add to 13, so 2, 3 and 5 are out. √391 is about 19.8, so the only primes left to test are 7, 11, 13, 17 and 19.
7 and 11
13
17
391 = 17 × 23, so it is not prime. It's a classic trap: a product of two primes close to its square root has no small factor to give it away.
Why You Only Test Up to the Square Root
Divisors come in pairs that multiply to the number: for 391, 17 × 23. In every pair, one member is at or below the square root and the other at or above it. If both were bigger than √n, their product would be bigger than n. So if nothing up to √n divides n, nothing above it can either.
You also only need to test primes, not every number: if 9 divided n, 3 would already have. Checking a five-digit number by hand means at most the 65 primes below 317.
Numbers That Look Prime but Aren’t
Odd numbers that don't end in 5 and aren't in the times tables most people know by heart often get mistaken for primes. 57 is known as "Grothendieck's prime" after the mathematician reportedly offered it as an example of a prime in a lecture.
| Number | Factors |
|---|---|
| 51 | 3 × 17 |
| 57 | 3 × 19 |
| 91 | 7 × 13 |
| 119 | 7 × 17 |
| 133 | 7 × 19 |
| 161 | 7 × 23 |
| 221 | 13 × 17 |
| 1,001 | 7 × 11 × 13 |
How Large Numbers Are Tested
Trial division up to √n becomes impossible quickly: a 30-digit number would need around 10¹³ divisions. This checker uses the Miller–Rabin test instead, which checks whether n behaves the way Fermat's little theorem says a prime must for a set of bases.
- Below 3,317,044,064,679,887,385,961,981 (about 3.3 × 10²⁴), testing the 13 bases 2 through 41 is proven to give the right answer every time.
- Above that, it uses 25 bases and reports a "probable prime". Each base that passes cuts the chance of a wrong answer by at least a factor of 4.
- Factors are found by trial division up to 10,000 and then Pollard's rho method, which finds factors of up to about 10 digits in a fraction of a second. If a composite has only larger factors, the checker still tells you it is composite.
The same tests underpin RSA encryption, which needs random primes of about 300 digits. Generating them is fast; factoring their product is what nobody can do quickly.
The Largest Known Prime
As of October 2024 the record is 2136,279,841 − 1, a Mersenne prime with 41,024,320 digits, found by the Great Internet Mersenne Prime Search. Mersenne numbers (2p − 1) have a fast special test, which is why nearly every record prime is one. Only 52 Mersenne primes are known.
Try 2147483647 in the checker: it's 2³¹ − 1, a Mersenne prime proved by Euler in 1772, and the largest value a signed 32-bit integer can hold.
Frequently asked questions
Why isn't 1 a prime number?
A prime has exactly two divisors, and 1 has only one. Leaving 1 out also keeps factorizations unique: otherwise 6 could be 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3.
Are there infinitely many primes?
Yes. Euclid's proof: multiply any finite list of primes together and add 1. The result leaves remainder 1 when divided by every prime on the list, so its prime factors must be new ones.
Can I paste a number with commas?
Yes. Commas, spaces and underscores are ignored, so 1,000,000,007 and 1 000 000 007 both work. Decimals and scientific notation are not accepted.
What are twin primes?
Pairs of primes two apart, such as 11 and 13 or 1,000,000,007 and 1,000,000,009. Nobody has proved whether there are infinitely many of them.
Sources
- OEIS A000040: the sequence of prime numbers.
- The Prime Pages: record primes, Mersenne primes and primality proofs.
- Great Internet Mersenne Prime Search (GIMPS): discovery of 2¹³⁶²⁷⁹⁸⁴¹ − 1 in October 2024.
- Sorenson & Webster, "Strong pseudoprimes to twelve prime bases", Mathematics of Computation 86 (2017): deterministic Miller–Rabin bounds for the first 13 prime bases.
Related Tools
Convert billion to trillion.
Convert crore to lakh.
Convert crore to million.
Turn a decimal into a simplified fraction.
Convert million to billion.
Convert million to lakh.