representation of a number as multiplication of its factors

Question

I want to represent a number as the product of its factors.The number of factors that are used to represent the number should be from 2 to number of prime factors of the same number(this i s the maximum possible number of factors for a number).

for example taking the number 24:

representation of the number as two factors multiplication are 2*12, 8*3, 6*4 and so on...,

representation of the number as three factors multiplication are 2*2*6, 2*3*4 and so on...,

representation of the number as four factors multiplication(prime factors alone) are 2*2*2*3.

please help me get some simple and generic algorithm for this

So given 24, what should this hypothetical function return? [2,12]? [8,3]? [3,8]? -- Also, I think you'll get a lot more response on a question like this if you try something and then come back with a specific question if it doesn't work. — mgilson, Feb 25 '13 at 14:03
have a look [here](http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python). That will give you the factors. Then you just have to manipulate them. — will, Feb 25 '13 at 14:03

will · Answer 1 · 2013-02-25T17:51:14.200

This will generate all the sets of factors which multiply to give the original number. It returns all the product sets as a unique list of sorted tuples.

The 1s are excluded, to avoid infinite recursion.

def prime_factors(n):    
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def product_sets(n):
    return set(products(1, [], n, prime_factors(n)))



def products(current_product, current_list, aim, factors):

    if current_product == aim:
        yield tuple(sorted(current_list))

    elif 0 < current_product < aim:
        for factor in factors:
            if factor != 1:
                for product in products(current_product * factor, current_list + [factor], aim, factors):
                    yield product


print list(product_sets(24))

Output:

[(4, 6), (3, 8), (2, 12), (2, 3, 4), (24,), (2, 2, 6), (2, 2, 2, 3)]

@user2095966 - perhaps you could mark it as the correct answer? — will, Feb 26 '13 at 13:07

score 0 · Answer 2 · answered Feb 25 '13 at 14:06

I know one...

If you're using python, you can use dictionary's to simplify the storage...

You'll have to check for every prime less than square root of the number.

Now, suppose p^k divides your number n, your task, I suppose is to find k. Here's the method:

int c = 0; int temp = n; while(temp!=0) { temp /= p; c+= temp; }

The above is a C++ code but you'll get the idea... At the end of this loop you'll have c = k

And yeah, the link given by will is a perfect python implementation of the same algorithm

score 0 · Answer 3 · answered Feb 25 '13 at 14:31

Here's a function that returns all the factors of a given number, n. Note that it returns every single factor, not a specific pair.

def factors(n):
    """Finds all the factors of 'n'"""
    fList, num, y, limit = [], n, 0, int(sqrt(n)) + 1
    for factor in range(1, limit):
        if n % factor == 0:
            if factor not in fList: fList.append(factor)
            y = n / factor
            if y not in fList: fList.append(y)
    return sorted(fList)

For example, factors(24):

>>> factors(24)
[1, 2, 3, 4, 6, 8, 12, 24]

representation of a number as multiplication of its factors

3 Answers3