Prime Factorization Calculator
Enter a positive integer to find its prime factorization — the unique product of prime numbers that equals the original number.
Enter a number above and click Calculate.
Formula & Method
Trial Division Algorithm:
- Divide n repeatedly by 2 until it is odd. Record the count as the exponent of 2.
- For each odd integer i from 3 up to √n, divide n repeatedly by i, recording the exponent.
- If the remaining value > 1 after the loop, it is itself a prime factor with exponent 1.
- Result: n = p₁e₁ × p₂e₂ × … × pₖeₖ
Number of Divisors: τ(n) = (e₁ + 1)(e₂ + 1)…(eₖ + 1)
Sum of Divisors: σ(n) = ∏ (pᵢeᵢ+1 − 1) / (pᵢ − 1)
Perfect Number: σ(n) − n = n → sum of proper divisors equals the number itself.
Assumptions & References
- Input must be an integer between 2 and 999,999,999.
- The Fundamental Theorem of Arithmetic guarantees every integer ≥ 2 has a unique prime factorization.
- 1 is not prime and has no prime factors; it is excluded by definition.
- Trial division runs in O(√n) time, which is efficient for numbers up to ~10⁹.
- Divisor formulas are multiplicative functions from elementary number theory (Hardy & Wright, An Introduction to the Theory of Numbers).
- Perfect numbers: Euclid–Euler theorem; only 6, 28, 496, 8128, … are known perfect numbers.