Prime Factorization Calculator

Prime factorization and why every number has a unique one

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written as a unique product of prime numbers, up to the order of the factors. This is one of the most important theorems in mathematics. It means that 360 can be written as 2 x 2 x 2 x 3 x 3 x 5, and no other combination of primes will multiply together to give 360. This uniqueness makes prime factorization a powerful tool for understanding numbers and solving problems that involve divisibility, fractions, and common factors.

This calculator finds the prime factorization of any positive integer up to one billion. It uses trial division, dividing the number repeatedly by the smallest possible prime until only 1 remains. The resulting prime factors are collected with their exponents (how many times each prime appears) and displayed in the compact exponential form you would see in a textbook: for example, 360 = 2^3 x 3^2 x 5. The calculator also lists every divisor of the number and shows the total count of divisors.

Knowing the prime factorization of a number lets you find its GCD with another number, calculate its LCM with another number, simplify fractions, determine whether a number is a perfect square or perfect cube, and count how many divisors it has. These are all standard tasks in number theory and algebra courses, and prime factorization is the common starting point for all of them.

The number of divisors can be computed directly from the prime factorization. If a number's factorization is p1^a1 x p2^a2 x p3^a3, then the total number of divisors is (a1+1) x (a2+1) x (a3+1). For 360 = 2^3 x 3^2 x 5^1, the divisor count is (3+1) x (2+1) x (1+1) = 4 x 3 x 2 = 24. This calculator computes the divisors directly by checking all integers from 1 to the square root of the number, which is accurate and efficient.

How prime factorization helps with fractions

Simplifying fractions requires finding the GCD of the numerator and denominator, and prime factorization makes that easy. To simplify 180/360, factor both: 180 = 2^2 x 3^2 x 5 and 360 = 2^3 x 3^2 x 5. The GCD is the product of the common prime factors taken at their lowest power: 2^2 x 3^2 x 5 = 4 x 9 x 5 = 180. Dividing both numerator and denominator by 180 gives 1/2. Without prime factorization, you would need to guess at common factors, which is slower and more error-prone for large numbers.

The same approach works for adding fractions with different denominators. To add 1/12 and 1/18, you need the LCM of 12 and 18. Factor them: 12 = 2^2 x 3 and 18 = 2 x 3^2. The LCM is the product of each prime at its highest power: 2^2 x 3^2 = 36. So 1/12 + 1/18 = 3/36 + 2/36 = 5/36. Prime factorization makes the process systematic and reliable.

Practical uses outside pure mathematics

Prime factorization has practical applications in scheduling, music theory, and computing. In scheduling, if you want to find the first time two repeating events coincide, you need the LCM of their cycle lengths, which requires factorization. In music, the ratios between musical notes correspond to simple fractions, and understanding these requires working with the factors of the frequencies involved. In computing, factorization underpins cryptographic algorithms and hash functions. This calculator handles the factorization step quickly so you can focus on applying the result to your specific problem.