Decomposing a number
Prime factorization writes an integer as a product of primes. The fundamental theorem of arithmetic guarantees this decomposition is unique apart from the order of the factors. For example, sixty equals two times two times three times five.
Trial division
The simplest method is trial division:
- Start with the smallest prime, two, and divide it out repeatedly while it divides the number.
- Move to three, then five, then each candidate, doing the same.
- Stop once the candidate squared exceeds the remaining value.
- Whatever number is left, if greater than one, is itself a prime factor.
You only need to test divisors up to the square root of the current value, because a number larger than that without a small factor must be prime.
Why it matters
Factorization underlies the greatest common divisor, least common multiple, and many number theory tasks. It is also the hard problem behind public key cryptography: multiplying primes is easy, but recovering them from a large product is believed to be very slow.
Key idea
Every integer has one unique prime factorization; trial division peels off prime factors from smallest upward, testing divisors only up to the square root.