Computing factors of a number →
Let’s look at a quick algorithm to compute all factors of a number N
. For example, if N
is 12
we want all the factors [1, 2, 3, 4, 6, 12]
. If N
is say 36
we want [1, 2, 3, 4, 6, 9, 12, 18, 36]
. We observe that:
1
andN
itself are always factors, of course.- Factors always occur in pairs.
(1, 12), (2, 6), (3, 4)
etc. IfN
is a perfect square, we also have(\sqrt(N), \sqrt(N))
.
From the above we realize that we don’t need to iterate through the numbers all the way until N
. We just need to do it until \sqrt(N)
. Here’s the algorithm for computing all the factors:
That was a super short post!