CODEWITHSUNDEEP
python
user2095966
user2095966

Reputation: 53

representation of a number as multiplication of its factors

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

Upvotes: 1

Views: 1939

Answers (3)

will
will

Reputation: 10650

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)]

Upvotes: 2

Rushy Panchal
Rushy Panchal

Reputation: 17532

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]

Upvotes: 0

Cheeku
Cheeku

Reputation: 873

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

Upvotes: 0

Related Questions