1

我想将一个数字表示为其因子的乘积。用于表示数字的因子的数量应该是从 2 到相同数量的素因子的数量（这是一个数字的最大可能的因子数量） .

例如取数字 24：

将数字表示为两个因子相乘是2*12, 8*3,6*4等等...,

将数字表示为三个因子相乘是2*2*6，2*3*4等等...，

将数字表示为四个因子乘法（仅素因子）是2*2*2*3。

请帮我获得一些简单而通用的算法

4

3 回答 3

2

这将生成所有乘以得到原始数字的因子集。它将所有产品集作为唯一的排序元组列表返回。

s 被排除在外，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)]
于 2013-02-25T14:46:56.597 回答
0

我知道一个...

如果您使用的是 python，则可以使用字典来简化存储...

您必须检查每个小于数字平方根的素数。

现在，假设 p^k 除以你的数字 n，我想你的任务是找到 k。这是方法：

诠释 c = 0; 国际温度 = n; while(temp!=0) { temp /= p; c+=温度；}

上面是一个 C++ 代码，但你会明白的......在这个循环结束时，你会有 c = k

是的，will给出的链接是相同算法的完美python实现

于 2013-02-25T14:06:20.540 回答
0

这是一个返回给定数字的所有因子的函数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]
于 2013-02-25T14:31:22.520 回答