Prime Number Checker
Instantly determine whether any positive integer is a prime number. Use it for number-theory homework, cryptography exercises, and checking factors quickly.
Last updated: September 2026
Prime? (1 = yes, 0 = no)
0
Formula below · 1 source (mathworld.wolfram.com) · Updated Sep 2026
Compare with similar
About this calculator
A prime number is an integer greater than 1 whose only positive divisors are 1 and itself; any integer greater than 1 that is not prime is composite. This checker uses trial division with the 6k ± 1 optimization. It first rules out 0, 1, and negatives as non-prime, treats 2 and 3 as prime, and eliminates any multiple of 2 or 3. After that, every prime greater than 3 has the form 6k − 1 or 6k + 1, so the algorithm tests only divisors of those forms, stepping i by 6 and checking i and i + 2. The loop runs while i·i ≤ n, because if n has a divisor larger than its square root it must also have a matching one smaller than the square root — so testing up to √n is sufficient. The result is 1 if the number is prime and 0 if it is not; for a composite number the tiles show its smallest prime factor and the matching cofactor. Edge cases: n ≤ 1 returns 0 (1 is neither prime nor composite, by definition, to keep unique factorization valid), 2 is the only even prime, and large inputs remain fast because the work grows only with √n. Trial division is exact but slower than probabilistic tests for very large cryptographic primes. Numbers up to 2⁵³ − 1 (about 9 × 10¹⁵) are checked exactly; the worst case, a large prime, takes about 30 million trial divisions, a fraction of a second.
How to use
Example (the default): 91. It is odd and not divisible by 3, so the checker tries 5 (no) and 7: 91 = 7 × 13, so the result is 0 (not prime), with smallest factor 7 and cofactor 13. 17: no divisor up to √17 ≈ 4.1 other than 1, so 17 is prime (result 1; smallest prime factor 17).
Frequently asked questions
Is 1 a prime number?
No. By the modern definition a prime must be greater than 1, so 1 is neither prime nor composite. This is not an arbitrary choice: it preserves the Fundamental Theorem of Arithmetic, which says every integer above 1 has a unique prime factorization. If 1 were prime you could insert any number of 1s into a factorization and uniqueness would be lost. The number 1 is instead called a 'unit'. This calculator therefore returns 0 (not prime) for 1, as well as for 0 and negative numbers.
Why is it enough to check divisors only up to the square root?
Because divisors come in pairs that multiply to n: if d divides n then so does n/d, and one of each pair is always less than or equal to √n. So if no divisor exists at or below √n, none exists above it either, and the number is prime. Checking all the way to n would be correct but wastefully slow, especially for large inputs. This square-root bound is the key efficiency idea behind trial division. A common beginner mistake is testing divisors up to n/2 or n, which works but is far slower than necessary.
What is the 6k ± 1 optimization the checker uses?
After removing multiples of 2 and 3, every remaining integer — and therefore every prime greater than 3 — is of the form 6k − 1 or 6k + 1. The algorithm exploits this by starting at 5 and stepping by 6, testing i and i + 2 each time, which skips roughly two-thirds of candidate divisors. This makes trial division about three times faster than checking every odd number without changing the result. It is exact, not probabilistic, so it never gives false primes. The trade-off is that for very large numbers even this is slow compared with specialized primality tests.
Why does 91 fool people into thinking it is prime?
91 is odd, not divisible by 3 or 5, and ends in 1, so it superficially resembles many primes — but 91 = 7 × 13. The mistake is stopping the divisibility checks too early, particularly forgetting to test 7. Numbers that are products of two mid-sized primes are the classic traps in mental primality checks. The lesson is to test every prime up to the square root (here up to 9, so 2, 3, 5, 7) before declaring a number prime. This calculator avoids the trap by systematically checking all required divisors.
When should I use a different tool?
For cryptographic-size numbers (hundreds of digits) trial division is far too slow; probabilistic tests such as Miller-Rabin are used instead. To find every prime factor of a composite number, use a prime factorization calculator.
Related calculators
Sources & references
Think a result is wrong? Report a problem with this calculator.