This note is one of many taken during 2025

Complete Factorization

April 9th 2025

Quick! what are all the factors of $720$ ?

Instead of giving you an answer, here’s an algorithm to find it.

First, by repeated division, find the prime factors.

\begin{align*} 720 / 2 &= 360 \\ 360 / 2 &= 180 \\ 180 / 2 &= 90 \\ 90 / 2 &= 45 \\ 45 / 3 &= 15 \\ 15 / 3 &= 5 \\ 5 / 5 &= 1 \\ \end{align*}

F_{0} = [2,\,2,\,2,\,2,\,3,\,3,\,5]

Find the all unique factors and their cartesian products in $F_{0}$ to create $P_{0}$ .

P_{0} = \{2,\,3,\,5,\,6,\,10,\,15,\,30\}

S_{0} = P_{0}

Remove one of each unique factor from $F_{0}$ to make $F_{1}$ .

F_{1} = [\,\cancel{2},\,2,\,2,\,2,\,\cancel{3},\,3,\,\cancel{5}]

Find the all unique factors and their cartesian products in $F_{1}$ to create $P_{1}$ .

P_{1} = \{\, 2,\,3,\,6 \,\}

Multiply each number in $P_{1}$ by each number in $S_{0}$ to find $S_{1}$ Remove any duplicate values and remove any values which had been found in previous $S_{n}$ .

\begin{align*} S_{1} = \{\,& 4,\,\cancel{6},\,10,\,12,\,20,\,\cancel{30},\,60\\ & \cancel{6},\,9,\,\cancel{15},\,18,\,\cancel{30},\,45,\,90\\ & \cancel{12},\,\cancel{18},\,\cancel{30},\,36,\,\cancel{60},\,\cancel{90},\,180 \}\\ S_{1} = \{\,& 4,\,10,\,12,\,20,\,60,\,9,\,18,\,45,\,90,\,36,\,180\} \end{align*}

Remove one of each unique factor from $F_{1}$ to make $F_{2}$ .

F_{2} = [\,\cancel{2},\,\cancel{2},\,2,\,2,\,\cancel{3},\,\cancel{3},\,\cancel{5}]

Find the all unique factors and their cartesian products in $F_{2}$ to create $P_{2}$ .

P_{2} = \{\, 2\, \}

Multiply each number in $P_{2}$ by each number in $S_{1}$ to find $S_{2}$ Remove any duplicate values and remove any values which had been found in previous $S_{n}$ .

\begin{align*} S_{2} &=\{\,8,\, \cancel{20},\, 24,\,40,\, 120,\, \cancel{18},\, \cancel{36},\, \cancel{90},\, \cancel{180},\, 72,\, 360\,\}\\ S_{2} &=\{\,8,\, 24,\,40,\, 120,\, 72,\, 360\,\}\\ \end{align*}

Remove one of each unique factor from $F_{2}$ to make $F_{3}$ .

F_{3} = [\,\cancel{2},\,\cancel{2},\,\cancel{2},\,2,\,\cancel{3},\,\cancel{3},\,\cancel{5}]

Find the all unique factors and their cartesian products in $F_{3}$ to create $P_{3}$ .

P_{3} = \{\, 2\, \}

Multiply each number in $P_{3}$ by each number in $S_{2}$ to find $S_{3}$ Remove any duplicate values and remove any values which had been found in previous $S_{n}$ .

S_{3} = \{\,16,\,48,\,80,\,240,\,144,\,720 \,\}

Remove one of each unique factor from $F_{3}$ to make $F_{4}$ .

F_{4} = [\,\cancel{2},\,\cancel{2},\,\cancel{2},\,\cancel{2},\,\cancel{3},\,\cancel{3},\,\cancel{5}]

Seeing as there are no more prime factors left in $F$ , Halt. The factors of $720$ are found in the union $S_0,\,S_1,\,S_2,\, S_3$ and of course $1$ .

\begin{align*} S &= \{1\}\cup S_0 \cup S_1 \cup S_2 \cup S_3 \\ S &=\{\\ &\phantom{=\{}1,\,2,\,3,\,4,\,5,\,6,\,8,\,9,\,10,\,12,\,15,\,16,\,18,\,20,\,24,\,30,\,36,\\ &\phantom{=\{}40,\,45,\, 48,\,60,\,72,\,80,\,90,\,120,\,144,\,180,\,240,\,360,\,720 \\ &\phantom{=\{}\} \end{align*}

I don’t know the name of this algorithm. I figured it out myself, but the simplicity of the algorithm leads me to believe it has been known for quite some time. There are likely more efficient algorithms, but compared to the naive algorithm of dividing by all numbers less than, it is appreciably efficient. An advantage of this algorithm is that it can be done on pen-and-paper and also can be done using a computer.

Example Python Program

This note is one of many taken during 2025