visualization

Factor Tree Calculator

Visualize prime factorization as an interactive factor tree diagram.

Back to Prime Factorization Calculator

Prime Factorization Tips

Click to show tips

Try an Example

Pick a scenario to see how the calculator works, then adjust the values

Highly Composite Number

Factor 360, a highly composite number with many divisors.

Key values: 360 = 2^3 x 3^2 x 5 · 24 divisors · phi(360) = 96

Large Prime

Check if 7919 is prime (it is -- the 1000th prime number).

Key values: 7919 is prime · 2 divisors · phi(7919) = 7918

GCD and LCM

Compute the GCD and LCM of 84 and 120.

Key values: 84 = 2^2 x 3 x 7 · 120 = 2^3 x 3 x 5 · GCD = 12, LCM = 840

Documentation

How to Read a Factor Tree

The factor tree is a binary diagram that splits each composite number into two factors: the smallest prime divisor (left branch) and the quotient (right branch). This process repeats until every branch ends at a prime number (highlighted as colored circles).

For example, the factor tree for 60:

60 splits into 2 and 30
30 splits into 2 and 15
15 splits into 3 and 5

The prime leaves (2, 2, 3, 5) give $60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$ .

Uniqueness of Factorization

The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization (up to the order of factors). No matter how you build the factor tree — choosing different factors at each step — the set of prime leaves is always the same.

Why 1 is not prime: If 1 were considered prime, factorization would not be unique: $6 = 2 \times 3 = 1 \times 2 \times 3 = 1^2 \times 2 \times 3$ , etc. Excluding 1 preserves the theorem's elegance.

The Trial Division Algorithm

This calculator uses an optimized trial division approach:

Divide by 2 while possible
Divide by 3 while possible
Test candidates of the form $6k \pm 1$ (i.e., 5, 7, 11, 13, 17, 19, ...) up to $\sqrt{n}$

The $6k \pm 1$ trick skips all multiples of 2 and 3, reducing trial count by ~2/3. Time complexity: $O(\sqrt{n})$ — at most 31,623 iterations for the maximum input of $10^9$ .

Frequently Asked Questions

What is a factor tree?

A factor tree is a diagram that breaks a composite number into its prime factors by repeatedly splitting it into two factors. Each branch ends at a prime number. For example, 60 splits into 2 and 30, then 30 into 2 and 15, then 15 into 3 and 5, giving $60 = 2^2 \times 3 \times 5$ .

Why does every number have a unique prime factorization?

The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization (up to ordering). No matter how you build the factor tree, the set of prime leaves is always the same.

Why is 1 not considered a prime number?

If 1 were prime, factorization would not be unique: $6 = 2 \times 3 = 1 \times 2 \times 3 = 1^2 \times 2 \times 3$ , and so on. Excluding 1 from the primes preserves the uniqueness guaranteed by the Fundamental Theorem of Arithmetic.

How does trial division work for factorization?

Trial division tests potential prime divisors starting from 2. Divide by 2 while possible, then by 3, then test candidates of the form $6k \pm 1$ (which skips multiples of 2 and 3) up to the square root of $n$ . This runs in $O(\sqrt{n})$ time.

Can a factor tree look different for the same number?

Yes, you can split a composite number into different factor pairs at each step (e.g., $12 = 2 \times 6$ or $12 = 3 \times 4$ ), but the final set of prime leaves is always identical. The tree shape may vary, but the factorization is unique.

More Math Calculators

Explore the category

Absolute Value Calculator

Area Calculator

Circle Calculator

Percentage Calculator

Pythagorean Theorem Calculator

Unit Circle Explorer