Prime Number Checker
Check if a number is prime, up to 40 digits. See the prime factorization, divisors, next and previous primes, and list every prime in a range.
How Prime Checking Works
A prime number is a whole number greater than 1 with exactly two divisors: 1 and itself. 2, 3, 5, 7 and 11 are prime. A number with more divisors, like 12 (1, 2, 3, 4, 6, 12), is composite. 0 and 1 are neither prime nor composite. Every whole number above 1 can be written as a product of primes in exactly one way, for example 360 = 2³ × 3² × 5.
To test n, divide it by each prime up to √n. If n = a × b, one of a or b must be √n or smaller, so a larger divisor cannot be the only one. If no prime up to √n divides n, then n is prime. For 221, √221 ≈ 14.9, and 221 ÷ 13 = 17, so 221 is not prime. This calculator uses trial division for numbers up to one trillion.
For bigger numbers, trial division is too slow, so the calculator uses the Miller–Rabin test. It checks a property that every prime has, using several test values called bases. With the first 13 primes as bases, the test is proven correct for every number below about 3.3 × 10²⁴. Above that, 20 bases are used and the result is called a probable prime. Composite numbers are split into factors with Pollard's rho method.
Disclaimer: This calculator performs standard mathematical operations for general and educational use only. We are not a substitute for professional review — for calculations where accuracy is critical, such as financial filings, engineering work, or academic submissions, please verify the result independently.
Frequently Asked Questions
About this calculator
This prime number checker tells you at once whether a whole number is prime. If it is not, you see its prime factorization and divisors. It also shows the previous and next prime, points out twin primes and Mersenne primes, and explains each step for numbers up to one trillion. Switch to the Primes in a Range tab to list every prime between two numbers.
What makes a number prime
A prime number is a whole number greater than 1 that has exactly two divisors: 1 and itself. 2, 3, 5, 7, 11 and 13 are the first primes. 2 is the only even prime, because every other even number can be divided by 2. A whole number above 1 that is not prime is called composite. 0 and 1 are neither prime nor composite.
Primes are the building blocks of all whole numbers. The fundamental theorem of arithmetic says that every whole number above 1 can be written as a product of primes in exactly one way, if you ignore the order. For example, 360 = 2³ × 3² × 5. This is the prime factorization that the checker shows for composite numbers.
How the checker works
Small and medium numbers (up to one trillion): trial division. To test n, the checker divides it by every prime up to √n. This is enough because if n = a × b, then a or b must be √n or smaller. If none of these primes divides n evenly, n is prime. For 1,000,000,007, √n ≈ 31,623, so the checker tries the 3,401 primes up to 31,622 and finds that none of them divides it.
Large numbers: the Miller–Rabin test. Above one trillion, the checker uses the Miller–Rabin test. Every odd prime p passes a check based on writing p − 1 = 2ˢ × d and raising a test value (a base) to the power d modulo p. A composite number fails this check for most bases. With the first 13 primes (2 to 41) as bases, the test is proven correct for every number below about 3.3 × 10²⁴. For larger numbers, the checker uses 20 bases and marks the result as a probable prime.
Factoring: Pollard's rho method. To split a large composite number, the checker first removes small prime factors, then uses Pollard's rho method, which finds a factor much faster than trial division. Numbers whose prime factors are all very large can take years to factor on any computer. In that case the checker shows the part it could not split.
Primes in a range: the sieve. The range tab uses a segmented sieve of Eratosthenes. It crosses out the multiples of each prime up to √(To), and every number left is prime. This lists up to one million numbers at a time, anywhere up to one trillion.
Worked examples
- 221: √221 ≈ 14.9, so the checker tests 2, 3, 5, 7, 11 and 13. 221 ÷ 13 = 17, so 221 = 13 × 17 is composite. Many people guess 221 is prime because it is odd and does not end in 5.
- 561: 561 = 3 × 11 × 17. It is the smallest Carmichael number, a composite number that fools the simple Fermat test for every base that shares no factor with it. The Miller–Rabin test does not have this weakness.
- 2,147,483,647: this is 2³¹ − 1, a Mersenne prime and the largest value of a signed 32-bit integer in programming. The checker confirms it is prime and labels it as a Mersenne prime.
- 600,851,475,143: = 71 × 839 × 1,471 × 6,857. Its largest prime factor, 6,857, is the answer to a well-known programming puzzle (Project Euler problem 3).
Primes get rarer as numbers grow, but they never run out. The prime number theorem says that near a number n, about 1 in every ln(n) numbers is prime. Near one trillion, ln(10¹²) ≈ 27.6, so a block of 200,000 numbers should hold about 7,238 primes. Between 999,999,800,000 and 1,000,000,000,000 there are 7,213, which you can check with the range tab.
Where prime numbers are used
- Internet security: RSA encryption multiplies two secret primes, each hundreds of digits long. Anyone can see the product, but no known method can factor it in a reasonable time, and that keeps the key safe.
- Programming: hash tables often use a prime number of slots to spread data evenly, and contest problems often ask for answers modulo the prime 1,000,000,007.
- Math records: the GIMPS project searches for very large Mersenne primes. In October 2024 it found 2^136,279,841 − 1, a prime with more than 41 million digits.
- Teaching: finding primes, factor trees and divisor counts are basic school topics, and the step-by-step working here shows each division.
- Instant prime check — Tests any whole number up to 40 digits and tells you if it is prime, composite, or neither (0 and 1).
- Prime factorization and divisors — Breaks composite numbers into prime factors with exponents, and lists the number of divisors and the divisors themselves.
- Step-by-step working — For numbers up to one trillion, shows √n, the primes tested, and the division that proves the answer.
- Primes in a range — Lists every prime between two numbers, up to one trillion and one million numbers at a time, with a count of twin prime pairs.
- Nearby primes and special primes — Shows the previous and next prime, and points out twin primes and Mersenne primes.