Prime Number Calculator

What this calculator does

Find out whether a number is prime, and if not, what it breaks down into. A prime number is a whole number greater than 1 that only 1 and itself divide evenly: 2, 3, 5, 7, 11, 13 and so on. Every other whole number above 1 is composite, meaning it can be split into smaller factors. Primes are the building blocks of multiplication, since every whole number breaks into primes in exactly one way.

Enter any whole number from 0 up to 2^64, about 18.4 quintillion. The calculator tells you whether it's prime. If it's not, it gives the smallest prime factor and the full breakdown into primes (the factorization). It also finds the next prime above your number and the previous prime below it. For numbers up to one million, it shows the number's place in the list of primes, too.

Where it's used

Why this math matters outside the classroom:

• Classroom checks. Fourth graders show that 91 is not prime because it splits into 7 × 13.
• Equal rows. A teacher with 23 students can't arrange them in a rectangle of more than one row, because 23 is prime.
• Cicada cycles. Periodical cicadas emerge every 13 or 17 years, and both of those cycle lengths are prime numbers.
• Online security. Encryption keys are built from very large primes, which computers test for primality in a fraction of a second.
• Hash tables. Programmers often size a hash table with a prime such as 101 so stored keys spread evenly across its slots.

Grade level and standards: Grade 4; Common Core State Standards for Mathematics 4.OA.B.4. © Copyright 2010. National Governors Association Center for Best Practices and Council of Chief State School Officers. All rights reserved.

How to use it

1. Type a whole number. Commas, spaces or underscores between groups of digits are ignored.
2. Read the answer at the top, then the smallest prime factor and the neighbouring primes.
3. Open the working to see the trial divisions or the Miller–Rabin rounds behind the answer.

What the inputs mean

Whole number to test

The number is entered as text, so values beyond 9 quadrillion keep every digit. Write it out in full, as ordinary digits. Short forms such as 1e18 aren't accepted. The upper limit is 2^64 = 18,446,744,073,709,551,616.

Formula and method

n is prime ⇔ n > 1 and no prime p ≤ √n divides n
n − 1 = 2^s × d   (d odd)
Miller–Rabin, base a: a^d ≡ 1, or a^(2^r × d) ≡ n − 1 (mod n) for some 0 ≤ r < s
bases a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Here n is your number and p is a prime being tried as a divisor. The ⇔ sign means 'exactly when'. In the Miller–Rabin lines, a is a test number called a base. The letters s and d come from splitting n − 1 into a power of 2 times an odd number d. 'x ≡ y (mod n)' means x and y leave the same remainder when divided by n.

For numbers up to 10^12, the calculator uses trial division: it tries dividing by primes one at a time. If n were composite, it would be a × b with a ≤ b, and then a ≤ √n. So it's enough to test divisors up to the square root, which is at most one million here. The first divisor found is the smallest prime factor.

Above 10^12, it uses the Miller–Rabin test. Fermat's little theorem says a^(n−1) ≡ 1 (mod n) when n is prime. A prime also has no square roots of 1 other than ±1, in this remainder arithmetic. Writing n − 1 = 2^s × d and squaring a^d again and again checks both facts at once. A base that breaks the pattern is a witness, proof that n is composite.

A single base can be fooled. But it has been proven, by checking every case by computer, that the first twelve primes (2 through 37) together catch every composite number below about 3.3 × 10^24. That makes the test certain, not a matter of chance, for every input this calculator accepts. When a number turns out to be composite, Pollard's rho method finds its factors.

Worked example

Is 221 prime?

1. The square root of 221 is about 14.866, so only the primes 2, 3, 5, 7, 11 and 13 need checking.
2. 221 is odd, and its digits add up to 5, so 3 doesn't divide it. It doesn't end in 0 or 5, and 221 ÷ 7 and 221 ÷ 11 leave remainders.
3. 221 ÷ 13 = 17 exactly, so 221 = 13 × 17.

Result: 221 is not prime. Its smallest prime factor is 13, the next prime is 223 and the previous prime is 211. There are 47 primes up to and including 221.

Understanding the result

A verdict of prime means no whole number other than 1 and the number itself divides it. For inputs above 10^12, this rests on the Miller–Rabin test with fixed bases. For numbers this size, that's a proof, not a probability.

The smallest prime factor is the first prime that divides the number. If it's close to the square root, the number is two primes of similar size multiplied together. Those are the hardest kind to factor.

The position shows where a prime sits in the list 2, 3, 5, 7, …. For example, 97 is the 25th prime. For a composite number, you see how many primes there are up to it instead.

Assumptions and limitations

• Inputs are whole numbers from 0 to 2^64, handled exactly with no rounding.
• Numbers above 2^64 are rejected. The fixed set of Miller–Rabin bases is proven only up to about 3.3 × 10^24, and the factoring step would slow down for much larger numbers.
• The position among the primes is given only for numbers up to 1,000,000.
• The working lists which bases were tested, but not every in-between square in each Miller–Rabin round.

Frequently asked questions

How this calculator is checked

Method: Trial division up to √n for n ≤ 10^12; deterministic Miller–Rabin with bases 2–37 (known to be exact below 3.3 × 10^24); Pollard's rho with Brent's cycle detection for factors; sieve of Eratosthenes for π(n). The calculation is covered by automated tests with known reference values and edge cases. Last updated 2026-10-18. Found a problem? Tell us.

Embed this calculator

Put this Prime Number Calculator on your own website or blog for free. Paste this code where you want it to appear: