Get combination of factors product of a given number

Question

I am not sure whether this question was posted before, after searching it, I cannot find it.

---

Question: Give one number, to print all factor product.

Example:

Given number: 20

Output: 1 * 20
        2 * 10
        2 * 2 * 5
        4 * 5

Given number: 30

Output: 1 * 30
        2 * 15
        2 * 3 * 5
        3 * 10
        5 * 6

---

Here are my thoughts:

Solution 1.

• step 1) First, get all prime factors of this number

  def get_prime_factors(n):
      factors = []
      if n == 0:
          return factors
  
      # Get the number of 2s that divide n
      while n%2 == 0:
          factors.append(2)
          n /= 2
  
      # n must be odd
      for i in range(3, int(ceil(sqrt(n))), 2):
          while n%i == 0:
              factors.append(i)
              n /= i
  
      # handle the case n is prime number greater than 2s
      if n > 2:
          factors.append(n)
  
      return factors
  

• step 2) Then get the combination of those factors

I plan to get all factor product through combination, however, I am stuck in how to handle those duplicate factors in this case? (question 1)

Solution 2:

Solve it through backtracking method.

def get_factors_recv(n, cur_ret, ret):
    for i in range(2, int(ceil(sqrt(n)))):
        if n%i == 0:
            fact_arr = [i, n/i]
            # add the current value to current result
            cur_ret.extend(fact_arr)
            if sorted(cur_ret) not in ret:
                ret.append(sorted(cur_ret))
                # backtracking
                cur_ret = cur_ret[:-2]
                get_factors_recv(n/i, cur_ret + [i], ret)


def get_all_factors_product(n):
    if n == 0:
        return '';

    result = []
    # push the simple factor multiplier
    result.append([1, n])

    get_factors_recv(n, [], result)

    return result

• I want to know is there any optimization for the above codes? (Question 2)
• Is there any better solution to solve it? (Question 3)

Answer 1

A simple while loop can solve your first problem of dupicates. Given a number:

num_list = []
i = 2;
num = 72*5*5*19*10

while i &lt=num:
    if(num%i == 0):
        num_list.append(i)
        num = num/i
    else:
        i = i + 1


print num_list

num_list will contain the factors. The idea is to not increase the index variable untill the number is no longer divisible by it. Also the number keeps reducing after every division so the loop will actually run a lot less iterations than the actual number. Instead of

while i&lt=num

you can also use

while i&lt=num/2

This is correct mathematically and results in further reduction of no of iterations.

This will give you all the factors.

Answer 2

Hope this helps.

number = 30
factors = []
for i in range(1, number+1):
  if number%i == 0:
     factors.append(i)

print factors