Prime Number Checker
Check whether any integer is a prime number instantly.
Did this tool answer your question?
Thanks — this helps us improve the tool.
How to use this tool
- Enter number in the fields above.
- Results update instantly as you type — or click Calculate.
- Read your result and the full breakdown beneath it.
Enter any positive integer to check whether it is a prime number.
Formula
A number n is prime if n ≥ 2 and no integer from 2 to ⌊√n⌋ divides it evenly.
Special cases: n < 2 → Not prime; n = 2 → Prime; even n > 2 → Not prime.
How it works
The calculator uses trial division with an early-exit optimisation: after ruling out numbers below 2 and even numbers above 2, it tests only odd divisors from 3 up to the square root of n. If any divisor divides n evenly the number is composite; if none do, it is prime. Checking only up to √n is sufficient because any factor larger than the square root must be paired with one smaller than it. The algorithm handles all non-negative integers exactly.
Worked example
- n = 17; √17 ≈ 4.12, so test odd divisors 3
- 17 mod 3 = 2 (not zero)
- No divisor up to ⌊√17⌋ = 4 divides 17
- Conclusion: 17 is prime
17 is Prime.
Common mistakes to avoid
- Classifying 1 as a prime number -- 1 is neither prime nor composite by definition; a correct primality check returns not-prime for 1.
- Assuming all odd numbers are prime -- odd composites such as 9, 15, and 25 fail the trial-division test up to sqrt(n) and are correctly identified as not prime.
- Expecting an instant result for very large numbers -- trial division up to sqrt(n) becomes slow for numbers with many digits; probabilistic algorithms are needed for large-scale primality testing.
Key terms
- Prime number
- A natural number greater than 1 that has exactly two distinct divisors: 1 and itself.
- Composite number
- A natural number greater than 1 that has at least one divisor other than 1 and itself; not prime.
- Trial division
- The simplest primality test: checking whether any integer from 2 to √n divides n exactly.
- Square root bound
- The optimisation that limits trial division to ⌊√n⌋: if n has no factor up to its square root it cannot have any factor above it either.
- Fundamental theorem of arithmetic
- Every integer greater than 1 can be represented uniquely as a product of prime numbers (up to ordering), making primes the building blocks of all integers.
Frequently asked questions
- What is a prime number?
- A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.