Prime Factorization Calculator

What is Prime Factorization?

Prime factorization is the process of breaking down a whole number into the product of the prime numbers that multiply together to give the original number. A prime number is a whole number greater than 1 that has no positive divisors other than 1 and itself (for example 2, 3, 5, 7, 11). For instance, the prime factorization of 360 is 2 × 2 × 2 × 3 × 3 × 5, which is written more compactly as 2³ × 3² × 5.

The Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every integer greater than 1 is either a prime number itself or can be written as a unique product of prime numbers, up to the order of the factors. This uniqueness is what makes prime factorization so powerful: no matter how you compute it, you always arrive at the same set of primes and exponents. It is the foundation for many topics in number theory, including the greatest common divisor, least common multiple, and modern cryptography.

How Trial Division Works

This calculator uses trial division. It first divides out all factors of 2, then tests odd divisors 3, 5, 7, … up to the square root of the remaining number. Each time a divisor divides evenly, it is recorded and divided out repeatedly to capture its exponent. If, after testing all candidates up to the square root, a value greater than 1 remains, that value is itself prime and is the final factor. You only need to test up to √n because if n had a factor larger than its square root, the matching co-factor would already have been found below the square root.

Related Calculators