Prime Number Checker

Primality and factorization

The simplest testing idea is trial division: if no integer from 2 up to √n divides n, then n is prime, you only need to go up to the root because if n = a·b, one of the factors is ≤ √n. That is great for small numbers but slow for huge ones. So the tool uses deterministic Miller-Rabin, which decides primality with a handful of modular exponentiations, and with the right witnesses gives an exact (not probabilistic) answer up to 10²⁴.

Factorization uses successive division: pull out the factor 2 while possible, then the odd numbers 3, 5, 7… up to the square root of the remaining number; whatever is left above 1 at the end is the last prime factor. The multiplicities become the output exponents. There are also two extra checks by integer roots: n is a perfect square if ⌊√n⌋² = n, and a perfect cube if ⌊∛n⌋³ = n.

• Trial division only needs to go up to √n.
• Deterministic Miller-Rabin: exact and fast up to 10²⁴.
• Factorization by successive division (2, then odds up to √n).
• Perfect square/cube checked via integer roots.

A prime and a factorization

Example 1, testing 97: since √97 ≈ 9.8, you only need to check the primes up to 9, namely 2, 3, 5 and 7. 97 is odd, its digit sum (16) is not divisible by 3, it does not end in 0 or 5, and 97 = 7 × 13 + 6, so 7 does not divide it either. No factor up to the root exists, so 97 is prime.

Example 2, factoring 360: pulling out 2, 360 = 2 × 2 × 2 × 45 = 2³ × 45; then 45 = 3 × 3 × 5 = 3² × 5. So 360 = 2³ × 3² × 5. Since not all exponents are even (there is a 3 and a 1), 360 is not a perfect square.

0, 1, the even prime 2 and where primes matter

A few values escape the prime/composite split: 0 and 1 are neither, 1 is called a unit, and the definition of prime requires n > 1. 2 is the only even prime, since any other even number has 2 as a factor. An elegant consequence of unique factorization: a number is a perfect square exactly when all its prime exponents are even, and a perfect cube when they are all multiples of 3.

Primes are the raw material of number theory and the foundation of much of modern cryptography: RSA, for example, relies on the fact that multiplying two large primes is easy, but factoring the product back is computationally very hard. They also appear in hash functions, pseudorandom generators and error-correcting codes.

• 0 and 1 are neither prime nor composite (1 is a unit).
• 2 is the only even prime.
• Perfect square ⇔ all exponents even; cube ⇔ multiples of 3.
• Uses: RSA cryptography, hashing, number theory.