Prime Factorization Calculator
Solve prime factorization problems step-by-step with our free calculator. See formulas, worked examples, and clear explanations.
Reviewed by Manoj Kumar, Mathematics Educator
Formula
n = p1^a1 * p2^a2 * ... * pk^ak (Fundamental Theorem of Arithmetic)
Every integer greater than 1 can be uniquely expressed as a product of prime numbers raised to positive integer exponents. Trial division tests each prime up to sqrt(n), dividing repeatedly. The number of divisors equals the product of (exponent + 1) for each prime factor.
Worked Examples
Example 1: Prime Factorization of 360
Problem:Find the complete prime factorization of 360 and determine the number of divisors.
Solution:360 / 2 = 180\n180 / 2 = 90\n90 / 2 = 45\n45 / 3 = 15\n15 / 3 = 5\n5 / 5 = 1\n\n360 = 2^3 * 3^2 * 5^1\n\nNumber of divisors = (3+1)(2+1)(1+1) = 4*3*2 = 24\nSum of divisors = (1+2+4+8)(1+3+9)(1+5) = 15*13*6 = 1170
Result:360 = 2^3 * 3^2 * 5 | 24 divisors | Sum = 1170 | phi(360) = 96
Example 2: Comparing Two Numbers via Factorization
Problem:Find the GCD and LCM of 252 and 198 using prime factorization.
Solution:252 = 2^2 * 3^2 * 7\n198 = 2 * 3^2 * 11\n\nGCD: Take minimum exponents of shared primes\nGCD = 2^min(2,1) * 3^min(2,2) = 2^1 * 3^2 = 2 * 9 = 18\n\nLCM: Take maximum exponents of all primes\nLCM = 2^2 * 3^2 * 7 * 11 = 4 * 9 * 7 * 11 = 2772\n\nVerification: GCD * LCM = 18 * 2772 = 49896 = 252 * 198
Result:GCD(252, 198) = 18 | LCM(252, 198) = 2772
Frequently Asked Questions
What is prime factorization and why is it unique?
Prime factorization is the process of expressing a composite number as a product of prime numbers. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has a unique prime factorization, aside from the order of the factors. For example, 360 = 2^3 * 3^2 * 5, and there is no other set of primes whose product is 360. This uniqueness is not trivial to prove and was rigorously established by Euclid and later refined by Gauss. The theorem serves as the cornerstone of number theory and has profound implications for mathematics. It ensures that prime numbers are truly the building blocks of all integers, analogous to atoms in chemistry. Without unique factorization, many fundamental theorems in algebra and number theory would fail.
How does the trial division method work for finding prime factors?
Trial division is the simplest and most intuitive algorithm for prime factorization. Start by dividing the number by the smallest prime, 2, and continue dividing by 2 as long as the result is even. Then try 3, then 5, and continue with each successive prime. For each prime, divide repeatedly until it no longer divides evenly, counting the number of times it divides (this count becomes the exponent). A crucial optimization is that you only need to test primes up to the square root of the remaining quotient, because if the quotient has no factor less than or equal to its square root, it must itself be prime. For example, factoring 84: 84/2=42, 42/2=21, 21/3=7, and 7 is prime. So 84 = 2^2 * 3 * 7. While trial division is slow for very large numbers, it works well for numbers up to about 10^12.
What is the relationship between prime factorization and finding divisors?
Prime factorization provides a complete recipe for generating all divisors of a number. If n = p1^a1 * p2^a2 * ... * pk^ak, then every divisor of n has the form p1^b1 * p2^b2 * ... * pk^bk where 0 <= bi <= ai for each i. The total number of divisors equals (a1+1)(a2+1)...(ak+1). For 360 = 2^3 * 3^2 * 5^1, the number of divisors is (3+1)(2+1)(1+1) = 4*3*2 = 24. The sum of divisors formula uses geometric series for each prime power: sigma(n) = (p1^(a1+1)-1)/(p1-1) * (p2^(a2+1)-1)/(p2-1) * ... This multiplicative structure arises because divisors of n correspond to choosing an exponent for each prime factor independently. These formulas are much faster than checking every number up to n for divisibility.
How is Euler totient function calculated from prime factorization?
Euler totient function phi(n) counts integers from 1 to n that are coprime to n (share no common prime factors with n). Using the prime factorization n = p1^a1 * p2^a2 * ... * pk^ak, the formula is phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk). Equivalently, phi(n) = p1^(a1-1)*(p1-1) * p2^(a2-1)*(p2-1) * ... For example, phi(360) = phi(2^3 * 3^2 * 5) = 2^2*(2-1) * 3^1*(3-1) * 5^0*(5-1) = 4*1*3*2*1*4 = 96. The totient function is multiplicative, meaning phi(a*b) = phi(a)*phi(b) when gcd(a,b) = 1. This function is central to RSA cryptography, where it determines the private key, and appears in many areas of number theory including Euler theorem: a^phi(n) is congruent to 1 modulo n for coprime a and n.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy