How to use it
Pick a part with the tabs at the top of the lab. The small Slovenčina link at the bottom of the lab switches its labels, messages and the line under the heading to Slovak, and English switches them back.
In Factor tree, type a whole number from 2 to 1,000,000,000,000 and press Start. In “You split” mode you build the tree yourself: select a square node, then pick a factor pair or type any divisor. Round nodes with a double border are primes, so a branch ends there. When every branch ends in a prime, the result appears in exponent form, for example 360 = 2³ × 3² × 5. Press “Try another tree” and start with a different first split: the tree looks different, but the primes at the ends never change. “Automatic” mode builds random trees, and the list under the controls compares every tree you finish.
Division ladder divides by the smallest prime again and again and explains each step. Prime sieve runs the Sieve of Eratosthenes on 1 to 100, 200 or 400. GCF & LCM puts the prime factors of two numbers into a Venn diagram.
Controls
- Mouse or touch: click or tap a square node, then a factor pair.
- Keyboard: Tab to a node and press Enter to jump to its factor pairs, then press Enter on a pair. In the row of tabs, the left and right arrow keys switch parts.
- Tree buttons: Undo removes the last split, Start over clears the tree, and Finish for me completes it with random splits.
- Ladder and sieve: Next step and Show all steps on the ladder; Next prime, Play/Pause, Finish and Reset in the sieve.
- Your number, tab, tree mode, sieve size, GCF numbers and language are remembered in this browser.
How it works
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. A composite number can be written as a product a × b with both factors greater than 1, and a factor tree repeats that split until only primes are left. The fundamental theorem of arithmetic says that every whole number greater than 1 is a product of primes in exactly one way, apart from the order of the factors. That is why every tree of the same number ends with the same primes. It is also why 1 is not a prime: if it were, you could add as many ones as you like, and factorizations would no longer be unique.
To test whether n is prime, it is enough to try primes up to √n: if n = a × b and both factors were bigger than √n, their product would be bigger than n. The division ladder divides by 2 as long as it can, then by 3, 5, 7 and so on, and when the next prime is bigger than the square root of what is left, what is left is prime. The lab keeps a list of all 78,498 primes below one million, which is enough for any number up to 1012.
The Sieve of Eratosthenes, named after a Greek scholar of the 3rd century BC, finds all primes up to N without dividing. Circle the smallest number that is not crossed out (it is prime), cross out its multiples, and repeat. Crossing out can start at p × p, because smaller multiples such as 2 × p have a smaller prime factor and are already gone. Once p × p is bigger than N, every number left is prime, so only the primes up to √N are needed. There are 25 primes up to 100, 46 up to 200 and 78 up to 400.
For two numbers a and b, the greatest common factor (GCF) uses each shared prime with the smaller exponent, and the least common multiple (LCM) uses every prime with the larger exponent. In the Venn diagram the shared primes sit in the overlap: the GCF is the product of the overlap, and the LCM is the product of everything in both circles. Together they use every prime factor of a and b exactly once, so
Things to try
- Build three different trees for 360 or 1024 = 210 and compare the primes at the ends.
- Put 1001 on the ladder and read why 2, 3 and 5 are skipped before 7 divides it.
- Run the sieve up to 100: 7 is the last prime that crosses anything out.
- In GCF & LCM, try 14 and 15 (nothing shared) and 8 and 40 (one divides the other).
- Enter 999,999,999,989, the largest prime below 1012: the tree cannot split at all.
Frequently asked questions
Why do different factor trees give the same answer?
The primes are fixed by the fundamental theorem of arithmetic; a tree only decides the order in which you find them.
What is the difference between a factor tree and the division ladder?
In a tree you may split a number into any two factors, for example 360 = 18 × 20. The ladder always divides by the smallest prime, so it follows one fixed path.
Can it factor bigger numbers?
This lab stops at 1012 so that the trees stay readable. For numbers with hundreds of digits, use the Prime Factorization Calculator.
Sources
- Stein W (2017). Elementary Number Theory: Primes, Congruences, and Secrets. The author’s free edition, chapter 1. The fundamental theorem of arithmetic and the prime sieve that stops at √n.