Prime Number Checker
Check whether a number is prime, see its full prime factorization and nearest neighboring primes, sieve all primes in a range, or test a Mersenne number 2ᵖ − 1 for primality with the Lucas–Lehmer test.
Written by Suhaib Hassan. Every algorithm is standard and independently re-checked. Our methodology.
Primality uses a deterministic Miller–Rabin test (exact, not probabilistic, for every integer below 2⁶⁴); factorization uses trial division; Mersenne numbers use the Lucas–Lehmer test.
It shows the actual divisibility trials and the Lucas–Lehmer iterations — not just a yes/no answer.
—
Primes near n
Prime gaps around the candidate.
Step-by-step working
—
Worked examples
A well-known prime
Is 104,729 prime?
Yes — it's the 10,000th prime
A Carmichael number
Is 561 prime?
No — composite, though it famously passes the simpler Fermat test for every base
A Mersenne prime
Is 2¹³ − 1 = 8191 prime?
Yes — 8191 is prime
What is a prime number?
A prime number is a whole number greater than 1 with exactly two positive divisors: 1 and itself. Every other whole number greater than 1 is composite, and by the Fundamental Theorem of Arithmetic, every composite number factors uniquely into primes.
How the tests work
- Trial division: test divisibility by every integer up to √n; if none divide evenly, n is prime.
- Miller–Rabin (deterministic here): a fast primality test that, using a fixed, proven set of witness bases, gives an exact yes/no answer for any n below 2⁶⁴ — no randomness or uncertainty involved.
- Lucas–Lehmer: for Mersenne numbers Mₚ = 2ᵖ − 1 with p prime, iterate s ← s² − 2 (mod Mₚ) starting from s = 4; Mₚ is prime exactly when the result is 0 after p − 2 steps.
By Suhaib Hassan · Reviewed 29 September 2026 · How CalculatePilot verifies formulas →
Sources
- Pomerance, C., Selfridge, J. L., & Wagstaff, S. S. (1980). The pseudoprimes to 25·10⁹. Mathematics of Computation 35(151), 1003–1026.
- Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer, chapters 3–4 (Miller–Rabin, Lucas–Lehmer).
- ISO 80000-2:2019, clause 6 (number theory notation).
Frequently asked questions
Is 1 a prime number?
No. By definition a prime has exactly two distinct positive divisors; 1 has only one (itself), so it is classified as neither prime nor composite.
Why does trial division only need to check up to √n?
If n = a × b with a ≤ b, then a ≤ √n. So if no divisor up to √n is found, no divisor beyond √n can exist either — every composite number has at least one factor at or below its square root.
What makes Carmichael numbers tricky?
A Carmichael number is composite but satisfies Fermat's little theorem for every base coprime to it, so the simple Fermat primality test wrongly calls it prime. Miller–Rabin with proper witnesses correctly identifies it as composite.
What is a Mersenne prime?
A prime of the form 2ᵖ − 1. p itself must be prime (a necessary but not sufficient condition) — for example, 2¹¹ − 1 = 2047 = 23 × 89 is composite even though 11 is prime. The largest known primes today are almost all Mersenne primes, found via the Lucas–Lehmer test.
How many primes are there?
Infinitely many — proved by Euclid around 300 BCE: assuming a finite list of primes and multiplying them together plus 1 always produces a number with a prime factor not on the list, a contradiction.
Why are primes important in cryptography?
RSA encryption relies on the fact that multiplying two large primes is fast, but factoring their product back into those primes is computationally hard — this asymmetry is what keeps the encryption secure.
Related calculators
Continue with number theory.