Prime Number Checker

Type an integer; the tool tells you whether it's prime and, if not, lists its prime factorization. For composite numbers it also shows the divisor pairs and the count of distinct prime factors.

Useful for quick number-theory checks, debugging crypto code where you need a prime of a specific size, or just satisfying curiosity about whether a particular number is prime. For numbers under 10^15 the result is exact (trial division up to √n). Above that, the tool uses Miller-Rabin probabilistic testing — very high confidence, but not a deterministic proof.

Reports execution time alongside the answer so you can see where the boundary between fast and slow lives.

For numbers below 10^15, the tool uses trial division up to sqrt(n), which is exact and fast for any value where the square root fits in a 32-bit integer. Above that, it switches to deterministic Miller-Rabin with a known set of witnesses (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) — a set proven sufficient to deterministically test all 64-bit integers. For inputs larger than 64 bits (BigInt territory), the tool runs probabilistic Miller-Rabin with 40 random rounds, giving a false-positive probability of less than 2^-80, which is the de-facto standard for cryptographic-grade primality testing.

Worked example. Input: 561. The tool tries dividers 2, 3, 5, 7, 11, 13, 17, 19, 23. 561 = 3 × 11 × 17, so trial division finds 3 quickly and the answer is composite, prime factors 3 × 11 × 17. Why 561 is interesting: it's the smallest Carmichael number — a composite that satisfies Fermat's little theorem for every base coprime to it, fooling the simpler Fermat primality test. Miller-Rabin correctly identifies it as composite by detecting the failure of a stronger condition (the existence of a non-trivial square root of 1).

Factorization for composite numbers uses Pollard's rho algorithm for sub-quadratic running time on large composites. For numbers with small factors, trial division finds them quickly; for semiprimes with two large factors (RSA-style), Pollard's rho is the fastest classical method short of dedicated quadratic-sieve / GNFS implementations. The tool handles factorization up to about 10^20 in reasonable time; beyond that, you're in research territory and want a library like SymPy or Mathematica.

Why primes matter beyond curiosity. RSA, ECC, Diffie-Hellman, Schnorr signatures — public-key cryptography relies on the difficulty of factoring products of large primes (RSA) or solving discrete log on prime-order groups (ECC). A 2048-bit RSA modulus is the product of two 1024-bit primes; factoring it is computationally infeasible with classical algorithms. Quantum computers threaten this assumption (Shor's algorithm), which is why post-quantum crypto research focuses on problems other than factoring.

Edge cases. 1 is not prime by convention — its factorization would otherwise break the fundamental theorem of arithmetic (unique factorization). 0 is not prime. Negative numbers are not prime in the standard definition (though some abstract algebra frameworks generalize the notion to Gaussian integers and other rings). The tool returns "not prime" with an explanation for these inputs.