Prime Factorization
Factor tree decomposition
About This Calculator
Prime factorization expresses any integer greater than 1 as a unique product of prime numbers. It is the foundation for computing GCD, LCM, simplifying fractions, and solving problems in cryptography and number theory.
Formula
Divide by the smallest prime factor, repeat on the quotient
Continue until the quotient equals 1
Express result as a product of prime powers: n = p1^a * p2^b * ...
Example Calculation
Prime factorization of 360
- 360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45
- 45 / 3 = 15, 15 / 3 = 5
- 5 is prime
360 = 2^3 x 3^2 x 5
Prime Factorizations of Common Numbers
| Number | Prime Factorization |
|---|---|
| 12 | 2^2 x 3 |
| 24 | 2^3 x 3 |
| 48 | 2^4 x 3 |
| 60 | 2^2 x 3 x 5 |
| 100 | 2^2 x 5^2 |
| 120 | 2^3 x 3 x 5 |
| 360 | 2^3 x 3^2 x 5 |
Frequently Asked Questions
Is the prime factorization of a number unique?
Yes. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization (ignoring order of factors).
How do I find the GCD using prime factorization?
Write both numbers as products of primes. The GCD is the product of all primes they share, each taken to the lowest power. For 12=2^2*3 and 18=2*3^2: GCD = 2^1 * 3^1 = 6.
What is a factor tree?
A factor tree is a diagram that repeatedly splits a number into two factors until all branches end in prime numbers. Reading the leaf nodes gives the complete prime factorization.