Prime Factorization Calculator

Understanding the prime factorization calculator — concept and principle

Prime factorization writes a whole number as a product of prime numbers, such as 360 = 2³ × 3² × 5. It is the basic tool behind simplifying fractions and roots, finding GCDs and LCMs, counting divisors, and understanding why some numbers behave the way they do. The calculator also reports how many divisors the number has, their sum, and whether the number is itself prime.

How it is calculated

• Trial division: divide n by 2 as many times as possible, then by 3, 5, 7 and so on, stopping when the trial divisor exceeds √n. Any value left above 1 is itself prime.
• Number of divisors: if n = p₁^e₁ × p₂^e₂ × … then d(n) = (e₁ + 1)(e₂ + 1)…
• Sum of divisors: σ(n) = ∏ (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1).

Valid inputs are whole numbers from 2 up to about 9 × 10¹⁵.

The principle

The fundamental theorem of arithmetic says every whole number greater than 1 has exactly one prime factorization, apart from the order of factors. Trial division only needs to go up to √n because if n = a × b, at least one of a or b is no larger than √n. A divisor of n is formed by choosing each prime's exponent independently, from 0 up to eᵢ, which gives eᵢ + 1 choices per prime and explains the divisor-count formula. Adding all those choices gives the sum formula, because (1 + p + p² + … + pᵉ) = (p^(e+1) − 1)/(p − 1) by the geometric series.

Worked example

1. Input: 360.
2. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, so 2³. 45 ÷ 3 = 15, ÷ 3 = 5, so 3². 5 is prime.
3. Prime factors: 2^3 × 3^2 × 5.
4. Number of divisors: (3 + 1)(2 + 1)(1 + 1) = 24.
5. Sum of divisors: (2⁴ − 1)/1 × (3³ − 1)/2 × (5² − 1)/4 = 15 × 13 × 6 = 1,170.
6. Is prime? no.

How to read the result

A single prime with exponent 1 means the number is prime. Many small primes, as in 360, mean many divisors, which is one reason 360 degrees in a circle and units like 12, 24 and 60 divide so conveniently. A sum of divisors greater than 2n means the number is abundant (360 is, since 1,170 > 720).

Common mistakes

• Treating 1 as a prime; it is neither prime nor composite.
• Stopping too early and leaving a composite factor such as 9 or 15.
• Forgetting to repeat a prime: 360 has three factors of 2, not one.
• Counting divisors with the exponents instead of exponents plus one.

Frequently asked questions

Why is factoring important in cryptography?

Multiplying two large primes is easy, but recovering them from the product is very hard for classical computers. RSA encryption relies on that difference.

How do I use a factorization to simplify a square root?

Pair equal primes: √360 = √(2² × 3² × 2 × 5) = 6√10.

Does every number have a unique factorization?

Every whole number above 1 does, apart from the order of the factors.

Sources: G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chapter 2 and Chapter 16 (arithmetical functions) · Euclid, Elements, Book VII, Propositions 30–32; Book IX, Proposition 14