Prime factorization (factor tree)

O(√n) per factor

Every integer above 1 factors uniquely into primes — the Fundamental Theorem of Arithmetic — and a factor tree shows that decomposition branch by branch. Take the current number, peel off its smallest prime factor as a leaf, and let the cofactor keep splitting on the right. When a node is already prime it becomes a leaf and the tree stops. Reading the leaves left to right gives the prime factorization. Finding each smallest factor by trial division costs O(√n), which is why factoring large numbers is hard — the security of RSA rests on exactly that difficulty. The left child at each split is the prime; the right child is what remains to factor.

Binary search tree
Press ▶ to run
Edit the input and press Play

How it works

  1. Find the smallest prime factor p of the current number.
  2. Split it into p (a leaf) and n/p.
  3. Recurse on n/p.
  4. Stop when the remaining number is prime.

Pseudocode

1factorTree(n):                      # O(√n) per factor2  p ← smallest prime factor of n3  if p = n:  return leaf(n)          # n is prime4  return node(n, leaf(p), factorTree(n / p))