0

If I was given the prime factorization of a number in the form [2, 2, 3, 5, 5] how would I be able to find all of the factors in the form [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]

I've attempted to do this through iterated loops, but as far as I was able to figure it out, it isn't clicking on a way to get the numbers as a result more than two numbers multiplying together

def find_factors(pfacts):
    pfacts = [1] + pfacts
    temp = []
    for i in pfacts:
        for j in pfacts[i+1:]:
            if i * j not in temp:
                temp.append(i * j)
    return [1] + temp

I know this isn't the right way to do it because it only finds a small number of the factors

[1, 2, 3, 5, 6, 10, 15]
Chris
  • 29,127
  • 3
  • 28
  • 51
blake
  • 59
  • 5
  • Just multiply all the number in your prime factorization, you will get a number and find factors of that number . Here is a great answer for getting factors https://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python. – Rahul May 30 '19 at 02:03
  • Above comment leads to a solution that is far less efficient, as the top answer in that answer has a solution that scales with the square root of N, where N is the product of your factors – Untitled123 May 30 '19 at 02:12
  • One thing to be weary of is the exponential increase in the combination of factors you will have to deal with. Consider [2]*100, it has only 101 factors, but using itertools.combinations will return 2^100 elements (give or take a factor of 2) – Untitled123 May 30 '19 at 02:15
  • @Untitled123 What is a better way to find factors then? – Rahul May 30 '19 at 02:50
  • @Rahul , the link that you posted has great answers of how to find factors given just a number N. Here, we are given all its prime factors already, and just need to combine them to find the rest. I think all the answers posted so far accomplish this. Consider a number N that is the product of huge primes (order of 10^100) of P and Q. It is a very difficult and computationally intensive process to find factors of N (without knowing P or Q), but given the prime factors P,Q, it is trivial to find that the factors of N are just 1, P, Q, N. – Untitled123 May 30 '19 at 03:15
  • @Untitled123 Ah, I had it the other way round, thanks. – Rahul May 30 '19 at 03:19

4 Answers4

3

One way is to use itertools.product with numpy.prod and numpy.power:

import numpy as np
from itertools import product

f = [2, 2, 3, 5, 5]
uniq_f = np.unique(f)
counts = np.array(list(product(*(range(f.count(i) + 1) for i in uniq_f))))
sorted(np.prod(np.power(uniq_f, counts), 1))

Output:

[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]
Chris
  • 29,127
  • 3
  • 28
  • 51
0

You could use itertools.combinations (which will give duplicates) and set to filter the duplicates out:

from itertools import combinations
from functools import reduce
from operator import mul

factors = [2, 2, 3, 5, 5]

set(reduce(mul, combination) for i in range (1, len(factors) + 1) for combination in combinations(factors, i))

Output:

{2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300}
gmds
  • 19,325
  • 4
  • 32
  • 58
0

Multiply all the combinations and add them to a set.

import itertools

def multiplyList(myList):
    # Multiply elements one by one
    result = 1
    for x in myList:
        result = result * x
    return result

factors=set()

stuff = [2, 2, 3, 5, 5]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        factors.add(multiplyList(subset))

factors=list(sorted(factors))

print(factors)

This works as below:

[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]
ohyesyoucan
  • 168
  • 2
  • 10
0

I am a touch newer to python so I have trouble understanding some of the things already posted. Here is my answer, it is longer but may be easier for a beginner to follow.

import numpy as np
import itertools

factors = [2, 2, 3, 5, 5]

al = []
for i in range(len(factors)):
    for combo in itertools.combinations(factors,i):
        al.append(np.prod(combo))

print(np.unique(al))

output:

[  1.   2.   3.   4.   5.   6.  10.  12.  15.  20.  25.  30.  50.  60.
  75. 100. 150.]
D. Price
  • 40
  • 5