数字的因子乘积表示法

Question

我想把一个数字表示成它的因数相乘的形式。用来表示这个数字的因数数量应该从2开始，到这个数字的质因数的数量为止（这是一个数字可能的最大因数数量）。

比如说我们来看数字24：

用两个因数相乘来表示这个数字的方式有 2*12、8*3、6*4，等等。

用三个因数相乘来表示这个数字的方式有 2*2*6、2*3*4，等等。

用四个因数相乘（只用质因数）来表示这个数字的方式是 2*2*2*3。

请帮我想一个简单通用的算法来实现这个。

Answer 1

这里有一个函数，它可以返回一个给定数字 n 的所有因子。需要注意的是，它会返回每一个因子，而不是特定的一对因子。

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)

举个例子，调用 factors(24) 的话：

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

Answer 2

我知道一个方法...

如果你在用Python，可以用字典来简化存储...

你需要检查所有小于这个数字平方根的质数。

现在，假设p的k次方能整除你的数字n，你的任务就是找出k的值。这里有个方法：

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

上面的代码是C++写的，但你能明白这个思路...

在这个循环结束时，你会得到c = k

对了，Will给的链接是这个算法在Python中的完美实现。

Answer 3

这段代码会生成所有可以相乘得到原始数字的因子组合。它会把所有的组合以独特的方式列出来，结果是一个排序好的元组列表。

为了避免出现无限循环，代码中排除了数字1。

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

输出结果：

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