Prime Number Checker

A prime number checker tests whether a whole number greater than 1 has any divisor besides 1 and itself. You only need to try primes up to its square root. For 91, √91 ≈ 9.54, and 91 ÷ 7 = 13, so 91 is not prime. For 97, none of 2, 3, 5 or 7 divides it, so 97 is prime.

How to use the prime number checker

1. On Is it prime?, type any whole number up to 24 digits, or an expression such as 2^31 − 1. The answer updates as you type.
2. Read the verdict, the prime factorization, the smallest prime factor, the number of divisors and the previous and next primes. For numbers up to 10,000,000 you also see the prime’s position, such as “the 25th prime”.
3. Open Show steps to see each trial division, or the Miller–Rabin test for large numbers.
4. On Primes in a range, enter two numbers to list and count every prime between them, with twin primes shaded and the largest gap.
5. On 1–100 chart, press Run the sieve or Next step to watch the Sieve of Eratosthenes. Tap any number to see why it is prime or what divides it.

What is a prime number?

A prime number is a whole number greater than 1 with exactly two divisors: 1 and itself. 13 is prime because only 1 and 13 divide it. A whole number greater than 1 that is not prime is composite: 15 = 3 × 5.

• 1 is not prime. It has only one divisor. It is neither prime nor composite.
• 2 is the only even prime. Every other even number is divisible by 2.
• 0 and negative numbers are not prime. Primes are defined only for whole numbers greater than 1.

How to check if a number is prime

Divisors come in pairs that multiply to n: for 91, the pair is 7 × 13. In every pair, one number is at most √n. So if no prime up to √n divides n, nothing else can either, and n is prime. This is the square root rule, and it is why the checker stops at √n.

1. Find √n and round down.
2. Divide n by each prime up to that number: 2, 3, 5, 7, 11, …
3. If one divides exactly, n is composite. If none does, n is prime.

Example 1: is 97 prime? √97 ≈ 9.85, so test 2, 3, 5 and 7. 97 is odd, its digit sum 16 is not a multiple of 3, it does not end in 0 or 5, and 97 ÷ 7 = 13 remainder 6. No prime up to 9 divides 97, so 97 is prime.

Example 2: is 221 prime? √221 ≈ 14.87, so test the primes up to 13. 2, 3, 5, 7 and 11 do not divide it, but 221 ÷ 13 = 17. So 221 = 13 × 17 is composite. It looks prime because its smallest factor is fairly large.

Example 3: is 1,001 prime? 1,001 ÷ 7 = 143, and 143 = 11 × 13. So 1,001 = 7 × 11 × 13 is composite.

Divisibility shortcuts

Prime numbers from 1 to 100

There are 25 primes up to 100:

The Sieve of Eratosthenes

To find all the primes up to a limit, you can cross out composites instead of testing each number. Write the numbers 2 to 100. Circle 2 and cross out its multiples from 4. The next number left, 3, is prime: cross out its multiples from 9. Do the same for 5 (from 25) and 7 (from 49). The next prime, 11, has 11 × 11 = 121, which is past 100, so you can stop. Every number left is prime. The chart tab animates these steps, and the range tab uses the same idea for ranges up to 10¹².

Checking very large numbers: the Miller–Rabin test

Trial division gets slow for large numbers. A 24-digit number would need testing up to about 10¹². For numbers above 10¹², the checker uses the Miller–Rabin test. It writes n − 1 = 2^s × d. Then, for a base a, it computes a^d mod n and squares the result up to s times. A prime always shows a specific pattern (1 at the start, or n − 1 along the way). If a base breaks the pattern, n is certainly composite.

Passing for one base does not prove a number is prime, but passing for the right set of bases does. Sorenson and Webster (2015) showed that every number below 3,317,044,064,679,887,385,961,981 (about 3.3 × 10²⁴) that passes for the 13 bases 2, 3, 5, …, 41 is prime. That is why this checker’s answers are exact, not “probably prime”, for every number up to 24 digits.

A simpler test is not enough. By Fermat’s little theorem, if n is prime then aⁿ⁻¹ mod n = 1. But 561 = 3 × 11 × 17 also gives a⁵⁶⁰ mod 561 = 1 for every a that shares no factor with 561. Numbers like this are called Carmichael numbers. Miller–Rabin catches them: base 2 shows that 561 is composite.

How many primes are there?

There are infinitely many primes, but they thin out. The prime number theorem says that near a number x, about 1 in ln(x) numbers is prime.

Twin primes are pairs of primes that differ by 2, such as (11, 13) and (41, 43). There are 8 pairs below 100 and 35 below 1,000. Nobody has yet proved whether there are infinitely many.

Common mistakes

• Calling 1 prime. A prime needs exactly two divisors; 1 has one.
• Assuming odd means prime. 9, 15, 21, 27 and 33 are odd composites.
• Missing the “look-alike” composites. 51 = 3 × 17, 57 = 3 × 19, 87 = 3 × 29 and 91 = 7 × 13 are often mistaken for primes.
• Stopping too early. Test every prime up to √n. For 221 you must reach 13.
• Testing too far. You never need to test past √n. For 97, stop at 7.

Prime numbers practice quiz: 10 questions

Test yourself with 10 multiple-choice questions. Choose an answer and press Submit to see if you are right and why. Your score appears at the end.

Frequently asked questions

Is 1 a prime number?

No. A prime has exactly two different divisors, and 1 has only one. It is neither prime nor composite. This keeps every whole number's prime factorization unique.

Is 2 a prime number?

Yes. Its only divisors are 1 and 2. It is the smallest prime and the only even one.

Is 51 a prime number?

No. Its digits add to 6, a multiple of 3, so 51 = 3 × 17.

How many prime numbers are there between 1 and 100?

25: 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.

What is the fastest way to check if a number is prime?

For numbers up to about 10¹², divide by the primes up to the square root. For larger numbers, use the Miller–Rabin test with a proven set of bases, as this checker does.

Sources

• Sorenson, J. P. and Webster, J. Strong Pseudoprimes to Twelve Prime Bases (2015), arXiv:1509.00864, Theorem 1.1

Related calculators

• Prime factorization calculator
• GCF and LCM calculator
• Factorial calculator
• Modular arithmetic calculator