We can find all the prime factors using a Sieve of Erastothenes. But how do we find ALL the factors of a number?
For instance, 24 = 2x2x2x3
But the complete factor list is – 1,2,3,4,6,8,12,24.
I am thinking of pushing all the factors in a vector, then using a bit mask to get each subset. The problems with this approach are-
-
The complexity will be O(n). For n=10^10, there are 35 factors, so 2^35 sets of factors, which is 10^10.
-
Repeated subsets. As the example above, we get multiple subsets with the same factors repeated, like (22….),(2.2…),(2..2..),etc. How to remove this redundancy?
Most simple solution:
for i = 1 to sqrt(n)
if i divides n put i and n/i into your result set
(make sure if i=n/i you put it only once there)
Complexity: O(sqrt(n))
(as long as you do not work with big numbers and can assume all basic arithmetic operations like test for divisibility as O(1).
A more sophisticated algorithm ist described here. First, find all prime factors of n including their powers dividing n (using the Sieve of Erastothenes). Then, create all combinations of those factors, as described in the blog post.
1