The idea: split until every piece is prime
A prime is a whole number above 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, … Any other number above 1 is composite: it is a product of two smaller numbers. A factor tree writes the number at the root and splits every composite node into two factors. When no node can split any more, every leaf is prime, and the number is the product of its leaves: 360 = 2 · 2 · 2 · 3 · 3 · 5 = 2³ · 3² · 5 (Demo: factor tree for 360).
Two ways to split
The page has two split rules. Smallest prime first divides off the smallest prime divisor each time, so one leaf comes off at every level and the tree is long and thin. Closest factor pair splits n into d × n/d with d the largest divisor that is at most √n, so the tree is bushier and shorter. Each split is shown in two steps: the two factors appear on the parent, then move down. A prime child turns the colour of its prime; the same colour marks that prime's row in the table.
Why the leaves are always the same
The fundamental theorem of arithmetic says every number above 1 is a product of primes in exactly one way, apart from the order. So any factor tree for 84 ends with two 2s, one 3 and one 7 (Demo: two different trees for 84). The key step is Euclid's lemma: if a prime p divides a product a · b, it divides a or b. Suppose two lists of primes had the same product. The first prime of one list divides the product of the other list, so by the lemma it divides, and so equals, one of the primes there. Cross both out and repeat until the lists are empty. The lemma itself comes from Bézout's identity, which the Euclidean Algorithm page computes.
Is it prime? Trial division up to √n
A node is a leaf when no number d with 2 ≤ d ≤ √n divides it. Checking beyond √n is not needed: if n = a · b and both a and b were larger than √n, the product would be larger than n. So one of the two factors is at most √n. For 97, √97 ≈ 9.85, and none of 2, 3, 5, 7 divides 97, so 97 is prime and its tree is just the root (Demo: a prime, 97). Only primes need to be tried, since a composite divisor would have a prime divisor that was tried first. To list all primes up to a limit at once, the Sieve of Eratosthenes crosses out multiples instead of dividing.
GCD and LCM from the exponents
Write both numbers over the same primes, with exponent 0 for a prime that is missing. A number d divides n exactly when every exponent of d is at most the exponent in n. So the greatest common divisor takes, prime by prime, the smaller exponent, and the least common multiple takes the larger one (Demo: GCD and LCM of 84 and 360):
| prime | 84 | 360 | min (gcd) | max (lcm) |
|---|---|---|---|---|
| 2 | 2 | 3 | 2 | 3 |
| 3 | 1 | 2 | 1 | 2 |
| 5 | 0 | 1 | 0 | 1 |
| 7 | 1 | 0 | 0 | 1 |
gcd(84, 360) = 2² · 3 = 12 and lcm(84, 360) = 2³ · 3² · 5 · 7 = 2520. For every prime, min + max is the sum of the two exponents, so gcd · lcm = a · b: 12 · 2520 = 30240 = 84 · 360. This method needs the factorization first, which is slow for big numbers. Euclid's algorithm finds the gcd without factoring anything, and then lcm = a · b / gcd.
Counting divisors
A divisor of 360 = 2³ · 3² · 5 picks an exponent 0–3 for 2, 0–2 for 3 and 0–1 for 5, and every choice gives a different divisor. So 360 has (3+1)(2+1)(1+1) = 24 divisors (Demo: number of divisors of 360). In general n = p₁e₁ ··· pkek has (e₁+1) ··· (ek+1) divisors. A prime has exactly 2, and 360 has more divisors than any smaller number, which is one reason it was chosen for the degrees of a circle.
Some quadratics, like Euler's n² + n + 41, never have a small prime factor, so their values are prime far more often than usual: see The Ulam Spiral: Primes on Diagonals.
What the page leaves out
Inputs are limited to 2…1000 so a tree fits its panel. Trial division takes about √n steps, which is hopeless for numbers with hundreds of digits: real factoring uses Pollard's rho, the quadratic sieve or the number field sieve, and RSA's security rests on how slow they still are. Deciding whether a big number is prime is much easier than factoring it (Miller–Rabin, AKS). Unique factorization also fails in some number systems, such as numbers of the form a + b√−5, where 6 = 2 · 3 = (1 + √−5)(1 − √−5).