How this calculator works
A prime number is a whole number greater than 1 that has no divisors other than 1 and itself. Every other whole number greater than 1 is composite, meaning it can be broken down into a product of smaller primes — the prime factorization.
This calculator checks whether a number is prime by trial division: testing whether any number up to its square root divides it evenly. If none do, the number is prime. It also reports the number's prime factorization, and the nearest prime numbers above and below it.
How the primality test works
A number n is prime if no integer from 2 up to √n divides it evenly.It is only necessary to check up to √n, because any factor pair (a, b) with a × b = n must have one factor ≤ √n.This calculator speeds up the search with the 6k ± 1 rule: after checking 2 and 3, every prime is of the form 6k − 1 or 6k + 1, so the loop only tests those candidates.This calculator supports numbers up to 10^12 (one trillion). Trial division up to √(10^12) = 1,000,000 is fast for a single check, but grows impractical for much larger numbers — cryptographic-scale primality testing uses entirely different probabilistic algorithms.
Worked example: is 561 prime?
- √561 ≈ 23.7, so only divisors up to 23 need checking.
- 561 ÷ 3 = 187 exactly, so 3 is a factor and 561 is not prime.
- Continuing the factorization: 187 ÷ 11 = 17 exactly, and 17 is itself prime.
- So 561 = 3 × 11 × 17. Notably, 561 is the smallest Carmichael number — a composite number that fools the simpler Fermat primality test for every base, which is why trial division (or a stronger test) matters.
Frequently asked questions
Is 1 a prime number?
No. By definition, a prime number must have exactly two positive divisors, 1 and itself. The number 1 only has one divisor (itself), so it is classified as neither prime nor composite.
Why check only up to the square root?
If a number n has a factor larger than √n, it must be paired with a corresponding factor smaller than √n (since their product is n). So if no factor exists at or below √n, none can exist above it either, making the square root a safe stopping point.
What is a Carmichael number?
A Carmichael number is a composite number that behaves like a prime under Fermat's primality test for every possible base, making that particular test unreliable. 561 is the smallest example (3 × 11 × 17). Trial division and other stronger primality tests correctly identify Carmichael numbers as composite.
How large a number can this calculator check?
Up to 10^12 (one trillion). Trial division needs to test roughly up to the square root of the input, so at 10^12 that's about a million checks — fast for a single query, but the method becomes impractical for much larger numbers.
Are there infinitely many prime numbers?
Yes. Euclid proved this over two thousand years ago: if you assume there were only finitely many primes, multiplying them all together and adding 1 produces a number that isn't divisible by any of them, so a new prime must exist — a contradiction that means the list of primes can never be complete.