Start with the definition and domain
A prime number is an integer greater than one with exactly two positive divisors: 1 and itself. A composite number is an integer greater than one with another positive divisor. Zero, one, and negative integers are neither prime nor composite under this elementary definition. Rejecting them first prevents an algorithm from confusing “no divisor found” with prime.
Two is prime and is the only even prime. Every even integer greater than two is divisible by two. Three is prime; any larger multiple of three is composite. Similar divisibility tests quickly eliminate many candidates before systematic checking. A decimal such as 29.0 may represent an integer mathematically, but the NumUtility input grammar requires digits only and does not accept decimal points or signs.
Why checking through the square root is enough
If n=ab is composite and both a and b were greater than √n, then ab would exceed n. Therefore at least one factor in a nontrivial factor pair is no greater than √n. Trial division only needs potential divisors through that boundary. It is enough to test prime divisors because a composite divisor itself has a smaller prime factor.
For 29, √29 is between 5 and 6, so test 2, 3, and 5. None divides, making 29 prime. For 35, testing 5 finds 35=5×7. Perfect squares make the inclusive boundary important: 49 has √49=7, and stopping before 7 would misclassify it. Use d×d≤n in exact integer code when a floating square root could round at a boundary.
A practical hand procedure
First confirm n is an integer greater than one. Handle 2 and 3 directly. Exclude even numbers and multiples of 3, then test possible prime divisors 5,7,11,13 and so on through √n. A 6k±1 pattern can skip multiples of 2 and 3, but not every number of that form is prime. The pattern is a filter, not a proof.
Input: 91. Rule: search prime divisors no greater than √91, which is less than 10. Steps: 91 is odd, digit sum 10 excludes 3, then 91÷7=13. Result: 91 is composite. Verification: 7×13=91. Input: 97. Rule: test 2,3,5,7 because √97<10. Steps: none divides. Result: 97 is prime. Verification: all possible smaller prime factors were exhausted.
Special and boundary examples
Input: 0, 1, 2, 3, and 4. Rule: apply the definition before trial division. Steps: 0 and 1 do not have exactly two positive divisors; 2 and 3 do; 4=2×2. Result: neither, neither, prime, prime, composite. Verification: list positive divisors for these small values.
Input: 29 and 35. Rule: test possible factors through each square root. Steps: 29 has no divisor among 2,3,5; 35 is divisible by 5. Result: 29 prime and 35 composite. Verification: 35=5×7 while the tested set exhausts candidates for 29. Input: 121. Rule: include the square-root endpoint. Steps: √121=11 and 121÷11=11. Result: composite. Verification: 11²=121.
Trial division versus Miller–Rabin
Trial division gives an intuitive proof but becomes slow as n grows because the square-root range grows. Miller–Rabin instead checks modular-exponent conditions that every prime must satisfy. With randomly chosen bases and a limited number of rounds it is commonly a probable-prime test: a passing result has a controlled error probability rather than automatic certainty for arbitrary sizes.
For bounded integer ranges, specific fixed witness sets can make Miller–Rabin deterministic. NumUtility first checks small primes and then uses the seven witnesses 2, 325, 9375, 28178, 450775, 9780504, and 1795265022, a set sufficient for unsigned 64-bit integers. Therefore its prime/composite result is exact throughout its documented accepted range, not merely “probably prime.” That guarantee must not be generalized to larger inputs or different witness sets.
Tool range and factor output
The Prime Number Checker accepts nonnegative digit strings from 0 through 18,446,744,073,709,551,615. It uses BigInt so values beyond JavaScript's safe Number integer range are not rounded. Negative signs, plus signs, commas, spaces within the number, decimals, and scientific notation are rejected. Values above the unsigned 64-bit maximum are rejected because the deterministic witness guarantee is scoped to that range.
For a composite result, the interface searches for an illustrative factor only up to 100,000 after checking two. A large composite can therefore be correctly classified without displaying a factor. Primality testing and complete factorization are different tasks. The tool is educational and is not a cryptographic prime generator, security assessment, or guarantee that an integer is suitable for any protocol.
Verification near the supported limit
Input: 18,446,744,073,709,551,557. Rule: apply the implementation's deterministic Miller–Rabin witnesses within the unsigned 64-bit range. Steps: small-prime screening and modular witness rounds all satisfy the prime conditions. Result: the project test suite classifies this value as prime. Verification: the automated test calls the same exact BigInt implementation and asserts true.
The maximum accepted value itself, 18,446,744,073,709,551,615, is composite; it is divisible by 3 because its decimal digit sum is divisible by 3. This distinguishes input limit from a claim that the limit is prime. For hand work, use trial division on modest values; for supported large inputs, rely on the documented deterministic method. If a value exceeds the bound, use a specialized arbitrary-precision system with an explicit proof or probability guarantee.
Divisibility evidence and proof standards
Quick divisibility rules are one-way filters. An even last digit proves divisibility by 2; a digit sum divisible by 3 proves divisibility by 3; and a last digit 0 or 5 proves divisibility by 5. Failing those tests does not prove prime. The number 91 passes all three but equals 7×13. Conversely, finding one proper factor proves composite immediately, so there is no need to list every factor before classifying it.
A prime claim must state what was exhausted. For a modest integer, testing all prime divisors through the square root is a deterministic proof. For a large bounded integer, a documented fixed-witness Miller–Rabin theorem can supply certainty. A few randomly selected Miller–Rabin rounds on arbitrary-size inputs justify only probable-prime language. The accepted range, witnesses, and arithmetic representation all matter; copying the method name without those conditions overstates the guarantee.
Performance and security are separate questions. A fast prime result does not mean the input was generated unpredictably, is large enough for a protocol, or satisfies any specialized structural requirement. Cryptographic systems require audited libraries and current standards. This checker neither generates candidates nor evaluates keys. Its exact 64-bit classification is appropriate for education and integer examples, not a professional security conclusion.
Input validation is part of a correct test. A blank string, 7.5, −7, or 1e3 is not an accepted candidate in this interface even when another parser might coerce it. Rejecting unsupported notation prevents silent rounding or a change of domain. Leading zeros do not change a valid digit string's integer value, but separators such as commas are not accepted. Copy a large input directly, then compare the echoed result with the source so a missing digit does not turn one legitimate prime question into another.