Prime Factorization

Every integer greater than 1 can be written as a product of primes, and that decomposition is unique — up to the order of the factors.

This result has a name: the fundamental theorem of arithmetic. It guarantees that 60 is always 2 × 2 × 3 × 5, and never another combination of primes.

The tool returns the factors, states whether the number is prime, and lists every divisor — which are the possible combinations of the factors found.

The method is successive division: divide by 2 while possible, then test odd numbers from 3 upward.

Testing stops when the divisor exceeds the square root of what remains. That works because if a number has a factor larger than its root, the complementary factor is necessarily smaller — and would already have been found.

Whatever remains at the end, if greater than 1, is prime and enters as the final factor.

That square root cut-off is what makes the method viable: testing whether 1,000,003 is prime needs about a thousand divisions, not a million.

Multiplying two large primes is instant. Recovering the two factors from the product is computationally expensive, and no fast method is known for the general case.

That asymmetry underpins RSA cryptography: the public key is the product, and security rests on nobody being able to factorise it in reasonable time.

Numbers of a few dozen digits factorise quickly here. Real cryptographic keys run to hundreds of digits, which is why they stay out of reach.