Prime Factorization Calculator
Solve prime factorization problems step-by-step with our free calculator. See formulas, worked examples, and clear explanations.
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.
Why is prime factorization important in cryptography?
The security of RSA encryption, the most widely used public-key cryptosystem, rests entirely on the difficulty of factoring large numbers. RSA uses a public modulus n that is the product of two large primes p and q, each typically 1024 bits or larger. While multiplying p and q to get n takes microseconds, factoring n back into p and q is computationally infeasible with current technology and algorithms. The best-known factoring algorithm, the General Number Field Sieve, has sub-exponential but super-polynomial running time. In 2020, a 829-bit number was factored as a research milestone, requiring enormous computational resources. RSA-2048 (a 2048-bit modulus) is expected to remain secure for decades. If efficient factoring algorithms were discovered, or if large-scale quantum computers implementing Shor algorithm become practical, RSA would be broken, which motivates ongoing research into post-quantum cryptography.
How do you compute GCD and LCM using prime factorization?
Prime factorization provides elegant formulas for the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. For the GCD, take the minimum exponent of each shared prime factor. For the LCM, take the maximum exponent of each prime factor appearing in either number. For example, with 360 = 2^3*3^2*5 and 84 = 2^2*3*7: GCD takes min exponents of shared primes: 2^min(3,2) * 3^min(2,1) = 2^2*3 = 12. LCM takes max exponents of all primes: 2^max(3,2) * 3^max(2,1) * 5^max(1,0) * 7^max(0,1) = 2^3*3^2*5*7 = 2520. The fundamental identity GCD(a,b) * LCM(a,b) = a*b always holds. While the Euclidean algorithm computes GCD more efficiently without factoring, the factorization approach gives deeper insight into the relationship and naturally extends to computing GCD and LCM of more than two numbers.