Factor Tree Explained: Prime Factorization Step by Step
How to build a factor tree by hand with a fully verified worked example, why every path through the tree lands on the same prime factors, and why factoring huge numbers is still genuinely hard even for computers.
A factor tree is one of the first real algorithms most people learn in school: a simple, repeatable procedure that always reaches the same destination no matter which path you take through it. This guide builds a factor tree by hand, verified digit by digit, shows why the path you choose never changes the final answer, and explains why factoring, despite being conceptually simple, is still a genuinely hard problem once numbers get large enough to matter for computer security. To find any number's complete list of factors instantly, the factor calculator lists every divisor and factor pair a number has, and the prime factorization calculator produces just the prime building blocks and their exponent form.
What a factor tree actually shows
Every whole number greater than 1 is either prime, meaning it has no factors besides 1 and itself, or composite, meaning it can be broken down into smaller factors. A factor tree makes that breakdown visible: start with the original number at the top, split it into any two factors that multiply back to it, then keep splitting each resulting factor the same way until every branch ends in a prime number. Reading off every prime at the end of every branch, the tree's leaves, gives the number's complete prime factorization, the unique set of prime numbers that multiply together to rebuild the original.
Every first split is a factor pair. The factor pairs of 30 are 1 x 30, 2 x 15, 3 x 10, and 5 x 6. Splitting 30 into 1 x 30 gets nowhere, since 30 comes straight back, but each of the other three pairs starts a tree that ends at the same leaves: 2, 3, and 5.
Worked example: the factor tree for 360
Start with 360 and split it into any valid factor pair. This example starts with 2 and 180.
360
/ \
2 180
/ \
2 90
/ \
2 45
/ \
3 15
/ \
3 5
Working down the tree: 360 = 2 x 180. 180 = 2 x 90. 90 = 2 x 45. 45 = 3 x 15. 15 = 3 x 5. Every branch now ends in a prime number (2, 3, or 5), so the tree is complete. Reading off every leaf: 2, 2, 2, 3, 3, 5.
Multiplying those six primes back together as a check: 2 x 2 = 4, times 2 = 8, times 3 = 24, times 3 = 72, times 5 = 360. That matches the original number exactly, confirming the tree is correct. Written in exponent form, 360 = 2^3 x 3^2 x 5.
A different starting split reaches the same answer
Starting from a different first factor pair demonstrates something worth trusting completely: the specific pairs you choose along the way never change the final set of primes.
360
/ \
4 90
/ \ / \
2 2 9 10
/ \ / \
(leaf) 3 3 2 5
This time, start by splitting 360 into 4 x 90 instead. 4 splits into 2 x 2, both already prime. 90 splits into 9 x 10. 9 splits into 3 x 3, both prime. 10 splits into 2 x 5, both prime. Reading off every leaf this time: 2, 2 (from the 4 branch), 3, 3 (from the 9 branch), 2, 5 (from the 10 branch). That is six primes total: 2, 2, 2, 3, 3, 5, exactly the same multiset as before, just reached by an entirely different route through the tree.
This is not a coincidence specific to 360. It is guaranteed by a result called the Fundamental Theorem of Arithmetic, which states that every whole number greater than 1 has exactly one prime factorization, no matter how you find it. You could start a factor tree for 360 from any of its valid factor pairs, 5 x 72, 6 x 60, 8 x 45, and every single one would still end with exactly 2, 2, 2, 3, 3, and 5 at the leaves.
Why some numbers branch more than others
The size of a factor tree, how many splits it takes to reach every prime leaf, depends on how many prime factors a number has, not on how large the number is. A number built from several small, repeated prime factors, like 360, branches several times. A prime number itself does not branch at all; it is a single leaf from the very first step, since it has no factor pair besides 1 and itself. Two numbers of similar size can have very different tree shapes for exactly this reason: 360 (2^3 x 3^2 x 5) branches six times before every leaf is prime, while 359, a prime number one less than it, does not branch at all.
Small cases show the pattern quickly. A prime stops at the very first step, and a prime power repeats a single leaf.
| Look-up | Factor tree leaves | Exponent form |
|---|---|---|
| Prime factorization of 8 | 2, 2, 2 | 2^3 |
| 27 factorization | 3, 3, 3 | 3^3 |
| Factorization of 41 | 41 (already prime, no branches) | 41 |
| Factorization of 71 | 71 (already prime, no branches) | 71 |
Using a prime factorization to find a GCF or LCM
Once a factor tree gives you a number's prime factorization, two other common problems become much easier: finding the greatest common factor (GCF) or least common multiple (LCM) shared between two numbers.
Worked example: the GCF of 360 and 150. From the tree above, 360 = 2^3 x 3^2 x 5. Factoring 150 the same way: 150 = 2 x 3 x 5^2. For the GCF, take the lower power of every prime that appears in both: 2^1 (lower of 2^3 and 2^1), 3^1 (lower of 3^2 and 3^1), and 5^1 (lower of 5^1 and 5^2). Multiplying: 2 x 3 x 5 = 30. Checking: 360 / 30 = 12, and 150 / 30 = 5, and 12 and 5 share no further common factor, confirming 30 is correct.
Worked example: the LCM of the same two numbers. For the LCM, take the higher power of every prime that appears in either number: 2^3, 3^2, and 5^2. Multiplying: 8 x 9 x 25 = 1,800. Checking with the GCF-based shortcut, LCM = (360 x 150) / GCF = 54,000 / 30 = 1,800, matching exactly.
This site's GCF calculator and LCM calculator both build on exactly this idea, and their own companion guides work through the prime factorization method for each in full detail alongside the alternative Euclidean algorithm and GCF-based shortcut.
How many factors a number has, straight from its prime factorization
A factor tree also answers a question that would otherwise mean counting every divisor by hand: how many total factors does a number have? Once a number's prime factorization is known, written in exponent form as a product of primes raised to powers, add 1 to each exponent and multiply those results together.
Worked example. 360 = 2^3 x 3^2 x 5^1. Add 1 to each exponent: 3+1=4, 2+1=3, 1+1=2. Multiply those: 4 x 3 x 2 = 24. So 360 has exactly 24 factors in total. This matches what a direct factor list confirms: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360, which is indeed 24 entries. This shortcut, adding 1 to each exponent and multiplying, works because each factor of the number corresponds to picking some number of copies of each prime, from 0 up to its full exponent, and multiplying the count of choices for each prime together (via the counting principle) gives the total number of possible combinations.
The same count works for any number. The table applies it to eight numbers that are looked up often, and the count in each row matches the length of the factor list beside it.
| Look-up | Prime factorization | Count from the exponents | All factors |
|---|---|---|---|
| 21 factors | 3 × 7 | (1+1)(1+1) = 4 | 1, 3, 7, 21 |
| 26 factors | 2 × 13 | (1+1)(1+1) = 4 | 1, 2, 13, 26 |
| 27 factors | 3^3 | 3+1 = 4 | 1, 3, 9, 27 |
| 32 factors | 2^5 | 5+1 = 6 | 1, 2, 4, 8, 16, 32 |
| 45 factors | 3^2 × 5 | (2+1)(1+1) = 6 | 1, 3, 5, 9, 15, 45 |
| 75 factors | 3 × 5^2 | (1+1)(2+1) = 6 | 1, 3, 5, 15, 25, 75 |
| 162 factors | 2 × 3^4 | (1+1)(4+1) = 10 | 1, 2, 3, 6, 9, 18, 27, 54, 81, 162 |
| 192 factors | 2^6 × 3 | (6+1)(1+1) = 14 | 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192 |
Why factoring large numbers is still a hard problem
Building a factor tree by hand is quick for numbers in the hundreds or low thousands, but the underlying method, checking candidate factors one at a time, gets dramatically slower as a number grows, and unlike many calculations in mathematics, nobody has ever found a fundamentally faster shortcut that works for every large number. This is not because mathematicians and computer scientists haven't tried; efficient integer factorization is a genuinely open problem, and the fastest known general-purpose methods, such as the general number field sieve used in serious computational research, still require an enormous, rapidly growing amount of computing time as the number of digits increases.
The real-world scale of this difficulty is well documented by RSA-768, a 232-digit number that was specifically constructed, and offered as a public challenge, to be difficult to factor. Factoring it was eventually completed in 2009, but only after roughly two years of sustained computation spread across hundreds of computers working in parallel, a research effort significant enough to be published as a landmark result in cryptography. That single example is why modern encryption, including the RSA algorithm that helps secure online banking and much of the encrypted web, is built specifically around this asymmetry: multiplying two large prime numbers together is fast, but factoring that product back apart, without already knowing one of the primes, is currently far beyond practical reach even for powerful computers, let alone by hand.
The practical takeaway is not that factoring is impossible, small and medium-sized numbers, the kind covered by a factor tree in school or by this site's own factor calculators, factor essentially instantly. The takeaway is that difficulty scales dramatically and unevenly with size: doubling the number of digits in a number does not double the work needed to factor it, it multiplies the work by a much larger amount, following a growth pattern far steeper than the simple multiplication needed to create the number in the first place. That steep, one-directional difficulty, easy to multiply two primes together, hard to reverse the process, is precisely the property modern cryptography depends on, and it's also exactly why choosing ever-larger prime numbers for encryption keeps staying ahead of ever-faster computers: each additional digit added to the primes involved adds a disproportionate amount of extra factoring difficulty for anyone trying to break the encryption without the key.
Factor trees, factor lists, and prime factorization: how the three relate
It is easy to blur these together, so it helps to separate what each one actually answers. A factor list (what this site's factor calculator produces) is every whole number that divides a number evenly, including composite ones: for 360, that list has 24 entries, from 1 up to 360 itself. A factor tree and a prime factorization (what the prime factorization calculator produces) both describe only the prime building blocks, 2, 2, 2, 3, 3, and 5 for 360; the tree is the step-by-step diagram that gets there, and the prime factorization is just the resulting list, often written compactly in exponent form as 2^3 x 3^2 x 5. Every entry in the full factor list can be rebuilt by multiplying some combination of those prime factors together: 2x2=4, 2x3=6, 2x2x3=12, 3x3x5=45, and so on, all the way up to the full product, 360, itself.
Practice example: a factor tree for 1,000
Round numbers like 1,000 are a good practice case because their factor trees are short and predictable, which makes them easy to double-check.
1000
/ \
10 100
/ \ / \
2 5 10 10
/ \ / \
2 5 2 5
Splitting 1,000 into 10 x 100 first: 10 splits into 2 x 5, both already prime. 100 splits into 10 x 10, and each of those splits again into 2 x 5. Reading off every leaf: 2, 5 (from the first 10), 2, 5 (from the first 10 inside 100), and 2, 5 (from the second 10 inside 100). That is three 2s and three 5s. Multiplying them back together: 2 x 2 x 2 x 5 x 5 x 5 = 8 x 125 = 1,000, confirming the tree is correct. In exponent form, 1,000 = 2^3 x 5^3, a clean, symmetric factorization that makes sense given that 1,000 is 10 cubed, and 10 itself is 2 x 5.
Why prime numbers matter beyond the classroom
Prime numbers can look like a purely academic curiosity, a label attached to a leaf on a factor tree, but two of the oldest and newest ideas in mathematics both depend directly on them.
RSA encryption, the scheme behind much of the padlock icon security on the modern web, is built on exactly the asymmetry described earlier in this guide. Setting up an RSA key starts by picking two large prime numbers and multiplying them together into a single number that becomes part of the public key; anyone can see that public key and use it to encrypt a message. Reversing the process, factoring that public number back into the two original primes, is what would be needed to break the encryption without the private key, and that reversal is the genuinely hard direction. Multiplying two large primes takes a computer a fraction of a second; factoring the resulting product back apart, without already knowing one of the primes, is the same open, dramatically slow problem covered earlier with RSA-768.
Finding primes in the first place has a much older solution: the Sieve of Eratosthenes, a method attributed to the Greek mathematician Eratosthenes roughly 2,200 years ago. Starting from a list of whole numbers from 2 up to some limit, it repeatedly takes the smallest number not yet crossed out, marks it prime, then crosses out every multiple of it. What survives without ever being crossed out is exactly the list of primes up to that limit, no factor tree or division required, just repeated elimination.
That method also clarifies why 1 is left out of the primes entirely. A prime number is defined as having exactly two factors, 1 and itself; the number 1 only has one factor, itself, so it fails that definition outright and is excluded from the sieve's very first step. Every other whole number greater than 1 sorts cleanly into one of two camps: prime, or composite, meaning it has more than two factors, the same divide a factor tree exists to explore.
How to factor numbers with a factor tree, without mistakes
A few habits keep a hand-drawn factor tree accurate. Always start by checking the smallest primes first, 2, then 3, then 5, then 7, since a number divisible by a small prime is usually easy to spot (even digits are divisible by 2; digits that sum to a multiple of 3 are divisible by 3; numbers ending in 0 or 5 are divisible by 5). Double-check each split by multiplying the pair back together before moving on, catching an arithmetic slip immediately rather than after several more branches have been built on top of it. And once every branch ends in a number you are confident is prime, do the full multiplication check described in the worked example above: multiply every leaf together and confirm the result matches the number you started with.