Math · Live
Prime Factorization Calculator,
tree, exponents & divisors.
Find the prime factorization of any integer up to 10 billion. Results include the exponent notation, an interactive factor tree, a step-by-step division ladder, and the complete sorted list of all divisors, with perfect square and cube detection.
Input
Factorize
Positive integer 1 – 9,999,999,999
Examples
- Type
- Composite
- # divisors
- 24
- Sum of divs
- 1,170
- Perfect □
- No
- Perfect ∛
- No
Prime factorization
n = 360
= 2 × 2 × 2 × 3 × 3 × 5
Visualisation
Factor tree
Step by step
Division method
| # | Number | ÷ Prime | = Result |
|---|---|---|---|
| 1 | 360 | 2 | 180 |
| 2 | 180 | 2 | 90 |
| 3 | 90 | 2 | 45 |
| 4 | 45 | 3 | 15 |
| 5 | 15 | 3 | 5 |
| 6 | 5 | 5 | 1 |
All divisors
24 factors of 360
Amber = prime factors. 1 and 360 are always divisors.
Number theory guide
What is prime factorization and why does it matter?
Prime factorization (also written prime factorisation) is the process of expressing a positive integer as a product of prime numbers. Every composite integer greater than 1 has exactly one prime factorization, a fundamental result known as the Fundamental Theorem of Arithmetic, proved by Euclid around 300 BCE.
For example, 360 = 2³ × 3² × 5. No other combination of primes multiplies to 360, and order doesn't matter; the factorization is unique up to rearrangement.
What is a prime number?
A prime number is a positive integer greater than 1 that has exactly two divisors: 1 and itself. The sequence of primes begins:
2 is the only even prime; all other primes are odd. There are infinitely many primes; Euclid proved this in Book IX of the Elements. The Prime Number Theorem tells us that primes become rarer as numbers grow: among integers near N, roughly 1 in ln(N) numbers is prime.
How to find the prime factorization: trial division
The standard algorithm is trial division: divide the number repeatedly by the smallest available prime until the quotient equals 1.
- Divide by 2 as many times as possible. Each successful division contributes a factor of 2.
- Divide by 3 as many times as possible.
- Continue with 5, 7, 11, 13, … (all primes in ascending order). A useful shortcut: only check numbers of the form 6k ± 1 after handling 2 and 3, since all other integers divisible by 2 or 3 are already eliminated.
- Stop when the candidate divisor exceeds √(remaining quotient). If the quotient at that point is greater than 1, it must itself be prime; add it as the last factor.
Example: factorize 360:
Reading a factor tree
A factor tree is a visual representation of prime factorization. Starting from the number at the top, each composite node branches into two factors. You continue splitting composite branches until every leaf is a prime number. The prime factorization is the product of all the leaf nodes.
This calculator builds the factor tree by always splitting off the smallest prime factor, creating a right-skewed tree:
In the tree above, amber (filled) nodes are prime; they are leaf nodes that cannot be split further. Grey nodes are composite intermediates.
Exponent (canonical) form
When a prime appears multiple times, we write it as a power (exponent). The canonical form lists prime factors in ascending order with their exponents:
Examples:
| n | Standard form | Exponent form | # divisors |
|---|---|---|---|
| 12 | 2 × 2 × 3 | 2² × 3 | 6 |
| 30 | 2 × 3 × 5 | 2 × 3 × 5 | 8 |
| 100 | 2 × 2 × 5 × 5 | 2² × 5² | 9 |
| 360 | 2 × 2 × 2 × 3 × 3 × 5 | 2³ × 3² × 5 | 24 |
| 1024 | 2 × 2 × … × 2 (10 times) | 2¹⁰ | 11 |
| 720720 | 2⁴×3²×5×7×11×13 (compact) | 2⁴×3²×5×7×11×13 | 240 |
Counting divisors from the factorization
If n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ, the number of positive divisors is:
Because each divisor is formed by choosing an exponent for each prime from 0 to eᵢ independently. For 360 = 2³ × 3² × 5¹:
You can verify: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360, exactly 24.
Sum of divisors: σ(n)
The sum of all positive divisors σ(n) also has a multiplicative formula:
For 360: σ(360) = (2⁴−1)/(2−1) × (3³−1)/(3−1) × (5²−1)/(5−1) = 15 × 13 × 6 = 1170. (Sum of all 24 divisors listed above = 1170.)
Perfect squares, cubes, and higher powers
A number is a perfect square if and only if all exponents in its prime factorization are even. A perfect cube requires all exponents divisible by 3. The pattern generalises:
- Perfect square: n = 36 = 2² × 3². All exponents (2, 2) are even. √36 = 6.
- Not a perfect square: n = 12 = 2² × 3. Exponent 1 is odd.
- Perfect cube: n = 1000 = 2³ × 5³. All exponents are multiples of 3. ∛1000 = 10.
Applications of prime factorization
- GCD and LCM: The greatest common divisor of two integers is the product of their shared prime factors (taking the lower exponent); the LCM uses the higher exponents. GCD(12, 18) = GCD(2²×3, 2×3²) = 2¹×3¹ = 6. LCM = 2²×3² = 36.
- Fraction simplification: Reducing a/b to lowest terms requires dividing by GCD(a, b), which prime factorization reveals directly.
- Cryptography: RSA encryption depends on the difficulty of factoring the product of two large primes. Multiplying two 1024-bit primes takes milliseconds; factoring the product is believed computationally infeasible for classical computers.
- Modular arithmetic: Euler's totient function φ(n), central to number theory, is computed from the prime factorization: φ(n) = n × Π(1 − 1/pᵢ).