Interactive Prime Factorization Tree

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].

Basic Examples

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.

Prime Factorization Tree of 2

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

Prime Factorization Tree of 2

Prime Factorization Tree of 3

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

Prime Factorization Tree of 3

Prime Factorization Tree of 4

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.

Prime Factorization Tree of 4

Prime Factorization Tree of 5

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

Prime Factorization Tree of 5

Prime Factorization Tree of 6

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.

Prime Factorization Tree of 6

Prime Factorization Tree of 12

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

Prime Factorization Tree of 12

Prime Factorization Tree of 20

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

Prime Factorization Tree of 20

Complex Examples

A couple examples of more complicated prime factorizations.

Prime Factorization Tree of 63

Prime Factorization Tree of 63

Prime Factorization Tree of 493

Prime Factorization Tree of 493

Prime Factorization Tree of 1581

Prime Factorization Tree of 1581

Prime Factorization Tree of 999997

Prime Factorization Tree of 999983

Prime Factorization Tree of 999983

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

Prime Factorization Tree of 999983