How this calculation works
A composite integer has a factor at or below its square root. If both factors were larger, their product would exceed the number.
Test divisors up to √nA worked example
97 has no divisor between 2 and 9, so it is prime.
Good to know
Numbers below 2 are neither prime nor composite.
Reference: NIST DLMF, Functions of Number Theory (opens in a new tab) ↗
Stop trial division at the square root
For the default input 97, the square root is about 9.85. Test integer divisors from 2 through 9. None divides 97 exactly, so the result is Prime. It is sufficient to test the primes 2, 3, 5 and 7 by hand, because a composite divisor would itself contain a smaller prime divisor.
The square-root stopping rule follows from factor pairs. If n = ab is composite, at least one factor is no greater than √n. Otherwise a and b would both exceed √n and their product would exceed n. Once all possible small factors are excluded, no untested large factor can form a valid pair.
Handle one and perfect squares explicitly
One is neither prime nor composite. A prime has exactly two positive divisors, 1 and itself, while 1 has only one. Zero is also outside the prime and composite classifications used here. The calculator returns Neither for these inputs.
Include the square-root endpoint when it is an integer. For 49, testing only divisors below 7 would miss 7 × 7. The Divisibility test calculator can verify an individual candidate divisor and its remainder. This bounded trial-division tool is intended for the supported integer range. Its method should not be interpreted as a practical way to test cryptographic-size integers.
A few questions, answered
Is two prime?
Yes. Its only positive divisors are 1 and 2. It is also the only even prime.
Does an odd input have to be prime?
No. Nine is odd and equals 3 × 3. Oddness only excludes divisibility by two.