Break any number into prime factors with factor tree visualization.
How to Use the Prime Factorization Calculator
Every whole number greater than 1 can be broken into prime building blocks in exactly one way. This calculator finds that unique breakdown and shows it as a factor tree, so you can see each split happen step by step.
- Enter any whole number. Type an integer up to one trillion. Larger numbers take slightly longer because there are more divisors to test.
- View the prime factors. The result shows each prime factor with its exponent, for example 360 as 2 cubed times 3 squared times 5.
- Follow the factor tree. Each composite number splits into two factors until only primes remain, giving you a visual map of the factorization.
- Use the result. Copy the factorization for homework, or feed it into GCD, LCM, and fraction-simplifying work.
Prime Factorization Calculator Formula
The method is trial division, optimized with a classic shortcut. First the calculator divides out all factors of 2, then all factors of 3. After that it only tests divisors of the form 6k minus 1 and 6k plus 1 — that is, 5, 7, 11, 13, 17, 19, and so on — because every prime larger than 3 sits next to a multiple of 6. This skips two-thirds of candidates with no loss of correctness.
Division stops at the square root of the remaining number, which is justified by a simple fact: every composite number has a prime factor no larger than its square root. If no divisor is found by then, the remainder itself must be prime. This guarantee is what makes the algorithm exact rather than approximate.
Underneath it all sits the Fundamental Theorem of Arithmetic: every integer greater than 1 has exactly one prime factorization, ignoring order. That uniqueness is why factorization is so useful — the prime breakdown is like a fingerprint for the number, and shared fingerprints reveal common divisors between numbers.
Example Calculation
Factor 360. Divide by 2: 360 gives 180, gives 90, gives 45 — three factors of 2, and 45 is odd so we move on. Divide by 3: 45 gives 15, gives 5 — two factors of 3. Now 5 is prime, so we stop. The factorization is 2 cubed times 3 squared times 5.
Check by multiplying back: 8 times 9 times 5 equals 360. The factor tree would show 360 splitting into 36 and 10, then 36 into 6 and 6, 10 into 2 and 5, and so on down to the primes 2, 2, 2, 3, 3, 5. Every path through the tree ends at the same primes — that is the Fundamental Theorem in action.
Using Prime Factorization to Find the GCD and LCM
Prime factorization earns its keep when two numbers meet. Write both in exponent form, and the greatest common divisor (GCD) and least common multiple (LCM) fall out by opposite rules.
Take 12 and 18: 12 = 2² × 3 and 18 = 2 × 3². For the GCD, take each shared prime at its lowest exponent: 2¹ × 3¹ = 6. For the LCM, take every prime at its highest exponent: 2² × 3² = 36. Both check out the slow way — 6 is the largest number dividing both, 36 the smallest both divide into.
The mnemonic: the GCD is strict — shared primes only, at their weakest — while the LCM takes everything at full strength. Our GCD Calculator and LCM Calculator run exactly this method.
Frequently Asked Questions
What is prime factorization?
It is the process of writing a whole number as a product of prime numbers. For example, 60 becomes 2 squared times 3 times 5. Because of the Fundamental Theorem of Arithmetic, this breakdown is unique — every number has exactly one, which makes it a reliable foundation for further math.
Why is prime factorization useful?
It is the engine behind simplifying fractions, finding greatest common divisors and least common multiples, and working with roots. In computer science it underlies RSA encryption, where the difficulty of factoring huge numbers keeps data secure.
What about the number 1?
The number 1 is neither prime nor composite, so it has no prime factorization — it is the empty product. This is not just a technicality; treating 1 as prime would break the uniqueness guaranteed by the Fundamental Theorem of Arithmetic.
How large a number can I factor?
This calculator handles integers up to one trillion. Trial division slows as numbers grow, but the square-root cutoff and the 6k shortcut keep it fast for anything in range. Factoring the enormous numbers used in cryptography would need entirely different algorithms.
How does the factor tree work?
You split the number into any two factors, then keep splitting each composite branch until every endpoint is prime. Different first splits give different-looking trees, but the prime leaves are always identical — try 60 as 6 times 10 versus 4 times 15 and watch both routes end at 2, 2, 3, 5.
What is the prime factorization of 100?
100 = 2² × 5². Trial division: 100 ÷ 2 = 50, 50 ÷ 2 = 25, 25 ÷ 5 = 5, 5 ÷ 5 = 1. The divisors collect as 2 × 2 × 5 × 5, or 2² × 5² in exponent form — and 4 × 25 = 100 confirms it.
Can a prime number be prime factorized?
A prime number is its own prime factorization: 7 factors only as 7, because a prime has exactly two divisors, 1 and itself, so there are no smaller building blocks. In exponent form it is 7¹.
Related Calculators
Try our Percentage Calculator and Fraction Calculator for more calculations.