Interactive Prime Factorization

This interactive generates the prime factorization tree for the given input number. The tree demonstrates how a number can be decomposed into a unique sequence of prime numbers (highlighted in green). This sequence of numbers is called the prime factorization of a number and is related to the Fundamental Theorem of Arithmetic. Each sequence is unique, meaning that no two numbers will have the same prime factorization. The product of the prime factorization of a number will always be equal to the number. Input is limited to the range [2,1000000].

Here are some examples of different prime factorization trees. Note, prime numbers will always have a tree with only a single node. This is because a prime number is defined as a number that is only divisible by itself and 1. Composite numbers, on the other hand, will have a more complicated tree.

The prime factorization tree of 2 only consists of a single node, because 2 is a prime number.

The prime factorization tree of 3 only consists of a single node, because 3 is a prime number.

The prime factorization tree of 4 is a tree with two leaf nodes 2 and 2. Since the number 4 can be decomposed into the two prime numbers 2 and 2 again.

The prime factorization tree of 5 only consists of a single node, because 5 is a prime number.

The prime factorization tree of 6 is a tree with two leaf nodes 2 and 3. Since the number 6 can be decomposed into the two prime numbers 2 and 3.

The prime factorization of 12 is 2, 2, and 3. The prime factorization corresponds with the leaf nodes of the tree.

The prime factorization of 12 is 2, 2, and 5.

A couple examples of more complicated prime factorizations.

The first prime number smaller than 1,000,000 is 999,983.