Prime Factorization Calculator
Solve prime factorization problems step-by-step with our free calculator. See formulas, worked examples, and clear explanations.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Prime Factorization Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: n = p1^a1 * p2^a2 * ... * pk^ak (Fundamental Theorem of Arithmetic)
Worked example — 360 = 2^3 * 3^2 * 5 | 24 divisors | Sum = 1170 | phi(360) = 96
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 180 / 2 = 90 90 / 2 = 45 45 / 3 = 15 15 / 3 = 5 5 / 5 = 1 360 = 2^3 * 3^2 * 5^1 Number of divisors = (3+1)(2+1)(1+1) = 4*3*2 = 24 Sum 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 198 = 2 * 3^2 * 11 GCD: Take minimum exponents of shared primes GCD = 2^min(2,1) * 3^min(2,2) = 2^1 * 3^2 = 2 * 9 = 18 LCM: Take maximum exponents of all primes LCM = 2^2 * 3^2 * 7 * 11 = 4 * 9 * 7 * 11 = 2772 Verification: 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.
What are perfect, abundant, and deficient numbers?
A number is classified based on the sum of its proper divisors (all divisors excluding the number itself). A perfect number equals the sum of its proper divisors, such as 6 = 1+2+3 and 28 = 1+2+4+7+14. An abundant number has a proper divisor sum exceeding itself, like 12 whose divisors 1+2+3+4+6=16 > 12. A deficient number has a proper divisor sum less than itself, like 8 whose divisors 1+2+4=7 < 8. Most numbers are deficient. Euler proved that all even perfect numbers have the form 2^(p-1) * (2^p - 1) where 2^p - 1 is a Mersenne prime. As of 2024, only 51 perfect numbers are known, all even. Whether odd perfect numbers exist remains one of the oldest unsolved problems in mathematics, with research suggesting they likely do not exist but no proof has been found.
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.
What is a square-free number and what is the radical?
A square-free number is one whose prime factorization contains no prime factor with an exponent greater than 1. In other words, no perfect square greater than 1 divides it. Examples include 6 = 2*3, 10 = 2*5, and 30 = 2*3*5. The number 12 = 2^2*3 is not square-free because 4 divides it. Approximately 60.79% of all positive integers are square-free, a result connected to the Riemann zeta function: the density equals 6/pi^2. The radical of a number n, denoted rad(n), is the product of all distinct prime factors of n, ignoring their exponents. For 360 = 2^3*3^2*5, the radical is 2*3*5 = 30. The radical essentially strips n down to its square-free core. The radical appears in the famous abc conjecture, one of the most important open problems in modern number theory, which relates the radical of the product abc to the magnitude of c.
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.
What are the omega and big-Omega arithmetic functions?
The lowercase omega function, written as omega(n), counts the number of distinct prime factors of n, ignoring their multiplicities. The uppercase Omega function, written as Omega(n), counts the total number of prime factors with multiplicity. For 360 = 2^3*3^2*5^1, omega(360) = 3 (three distinct primes: 2, 3, 5) and Omega(360) = 6 (three 2s, two 3s, and one 5). The Hardy-Ramanujan theorem proves that for most large numbers n, omega(n) is approximately ln(ln(n)), a remarkably slow-growing function. This means typical large numbers have relatively few distinct prime factors. The Erdos-Kac theorem further shows that omega(n) follows a normal distribution centered at ln(ln(n)) with standard deviation sqrt(ln(ln(n))). These results reveal the statistical regularity hidden within the seemingly chaotic distribution of prime factors.
What modern algorithms exist for factoring very large numbers?
Beyond trial division, several sophisticated algorithms handle large numbers. The Pollard rho algorithm uses cycle detection in a pseudo-random sequence modulo n, efficiently finding factors up to about 10^15. The elliptic curve method (ECM) uses arithmetic on elliptic curves over finite fields and excels at finding medium-sized factors (up to about 60 digits) regardless of the size of n. The quadratic sieve searches for numbers whose squares are congruent modulo n and combines them to find factors, working well up to about 100 digits. The General Number Field Sieve (GNFS) is the fastest known algorithm for numbers above 100 digits, using algebraic number theory to construct the required congruences. Its running time is sub-exponential: roughly e^(c * (ln n)^(1/3) * (ln ln n)^(2/3)). Shor quantum algorithm could factor in polynomial time, but requires a fault-tolerant quantum computer that does not yet exist.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Greatest Common Factor Calculator
Find the GCF (GCD) of two or more numbers using prime factorization and Euclidean algorithm.
🧮Least Common Multiple Calculator
Find the LCM of two or more numbers using prime factorization and the GCF method.
🧮Euler Totient Calculator
Calculate Euler totient function for any positive integer with prime factorization.
🧮Prime Number Calculator
Calculate prime number with inputs, formulas, and instant results.
🧮Relatively Prime Calculator
Calculate relatively prime with inputs, formulas, and instant results.
🧮Factorization Visualizer
Calculate factorization visualizer with inputs, formulas, and instant results.
🧮Mersenne Prime Finder
Calculate mersenne prime finder with inputs, formulas, and instant results.
🧮Prime Counting Function Calculator
Calculate prime counting function with inputs, formulas, and instant results.