Prime Factorization Calculator

Prime factorization (also called integer factorization) expresses any whole number greater than 1 as a product of prime numbers — numbers like 2, 3, 5, 7 and 11 that have no divisors other than 1 and themselves. This calculator takes an integer from 2 up to 1,000,000, finds its complete prime factorization, tells you whether the number is itself prime, and shows the step-by-step factor tree it used to get there. It is built for students learning number theory, anyone simplifying fractions, square roots or ratios, and people who need to find a greatest common factor (GCF) or least common multiple (LCM) reliably.

The result is meaningful because of the Fundamental Theorem of Arithmetic: every integer greater than 1 has exactly one prime factorization, ignoring the order of the factors. That uniqueness is what makes the prime factorization such a useful fingerprint of a number. For example, 360 always breaks down to 2³ × 3² × 5 and nothing else. The same idea underpins modern cryptography — RSA encryption is secure precisely because multiplying two large primes is fast while factoring their product back apart is, with current methods, computationally infeasible.

How it works

The method is trial division. Starting from the smallest prime, 2, you repeatedly check whether it divides the number evenly. Each time it does, you record that prime as a factor and replace the number with the quotient. When 2 no longer divides cleanly, you move on to 3, then 5, 7 and so on. You only ever have to test divisors up to the square root of the current value: if no prime below the square root divides it, whatever is left must itself be prime. The process stops when the quotient reaches 1, and the list of recorded primes — written with exponents for repeats — is the answer.

Worked example

Take 72. Divide by 2: 72 ÷ 2 = 36. Again: 36 ÷ 2 = 18. Again: 18 ÷ 2 = 9. Now 2 no longer divides evenly, so move to 3: 9 ÷ 3 = 3, then 3 ÷ 3 = 1. We used 2 three times and 3 twice, so 72 = 2³ × 3². A factor tree shows the same thing visually: split 72 into 8 × 9, then 8 into 2 × 2 × 2 and 9 into 3 × 3 — the leaves of the tree are exactly the prime factors.

Using it for GCF and LCM

Once you have the prime factorizations of two numbers, comparing exponents gives you both GCF and LCM instantly. For the GCF, take the smallest exponent of each shared prime; for the LCM, take the largest exponent of every prime that appears in either number. For instance, 12 = 2² × 3 and 18 = 2 × 3², so the GCF is 2¹ × 3¹ = 6 and the LCM is 2² × 3² = 36.

Tips and common mistakes

A frequent slip is treating 1 as a prime — it is not, and a prime factorization never includes a factor of 1. Likewise, the number you start with must be a positive integer greater than 1; decimals are floored to a whole number before factoring. Remember that the exponent notation is just shorthand for repetition: 2³ means 2 × 2 × 2 = 8, so 2³ × 3² is 8 × 9 = 72, not 2 × 3 added in some way. If the calculator reports a number as prime, it genuinely has no factors other than 1 and itself — that is the correct, complete answer, not a sign that factoring failed.