Prime Factorization Calculator
Breaks any positive integer into its unique product of prime factors, displayed as a multiplication string or using exponent notation. Ideal for simplifying fractions, finding GCDs, LCMs, and studying number theory.
About this calculator
Every integer greater than 1 can be written uniquely as a product of primes — this is the Fundamental Theorem of Arithmetic. For a number n, the factorization is expressed as n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ, where each pᵢ is a distinct prime and eᵢ is its multiplicity. The calculator uses trial division: it tests each integer i from 2 upward, dividing n by i as many times as possible before moving to the next candidate. Because any composite factor of n must have a prime factor ≤ √n, the loop only needs to run up to √n, making it efficient for typical inputs. The result can be shown as a flat multiplication list, in compact exponential form, or as a comma-separated list.
How to use
Factor the number 360. Enter 360 in the 'Number to Factor' field and choose 'exponential' display format. The algorithm divides by 2 three times (360 → 180 → 90 → 45), by 3 twice (45 → 15 → 5), and once by 5, leaving 1. The prime factors collected are [2, 2, 2, 3, 3, 5]. Grouping by exponent gives 2³ × 3² × 5¹. The calculator displays this as 2^3 × 3^2 × 5. Verify: 8 × 9 × 5 = 360. ✓ You can also use this result to find that the number of divisors of 360 is (3+1)(2+1)(1+1) = 24.
Frequently asked questions
Why is prime factorization useful for finding the GCD and LCM of two numbers?
Once you have the prime factorizations of two numbers, the GCD is the product of primes raised to the minimum exponent appearing in both, and the LCM is the product of primes raised to the maximum exponent in either. For example, 360 = 2³·3²·5 and 252 = 2²·3²·7, so GCD = 2²·3² = 36 and LCM = 2³·3²·5·7 = 2520. This approach is far more systematic than listing all divisors, especially for large numbers. It also directly simplifies fractions by dividing numerator and denominator by the GCD.
What is the Fundamental Theorem of Arithmetic and why does it matter?
The Fundamental Theorem of Arithmetic states that every integer greater than 1 has a factorization into primes that is unique up to the order of factors. This uniqueness is what makes prime factorization a reliable fingerprint for every number. It underpins much of number theory — from proofs that √2 is irrational to the security of RSA encryption, which depends on the practical difficulty of factoring very large numbers. Without uniqueness, arithmetic operations like GCD and LCM would not have well-defined answers.
How does trial division work and when does it become slow?
Trial division tests every integer from 2 up to √n as a possible factor, dividing out each one completely before moving on. Its time complexity is O(√n), which is fast for numbers up to a few billion but grows impractical for very large numbers — a 20-digit number would require checking up to 10¹⁰ candidates. For cryptographic-scale numbers (hundreds of digits), specialized algorithms like the quadratic sieve or general number field sieve are used instead. For everyday use in homework, competition math, or fraction simplification, trial division is perfectly sufficient.