从Python中的素因子列表创建所有可能的因子

2024-03-29 09:41:55 发布

您现在位置:Python中文网/ 问答频道 /正文

虽然我看到了一些关于寻找素数因子和除数的帖子,但我还没有找到关于Python中因子分解的问题的答案。我有一个素数因子的列表,即对于24,它是[2,2,2,3]。我想从这个列表中得到所有可能的因子,即对于24的输出应该是[[2,12], [3,8], [4,6], [2,2,6], [2,3,4], [2,2,2,3]]。 我尝试过itertool方法,但是这会产生很多重复的答案,并且忘记了其他答案(比如查找[2,3,4],但是忽略了[4,6])。在

我特别感兴趣的是一种使用生成的素数因子列表的方法。我找到了一个递归函数的解决方法。在

def factors(n, n_list):                 
    for i in range(2, 1 + int(n ** .5)):
        if n % i == 0:
            n_list.append([i, n // i])
            if n // i not in primes:  #primes is a list containing prime numbers
                for items in factors(n // i, []):
                    n_list.append(sorted([i] + items))
    fac_list = [[n]]                  #[n] has to be added manually
    for facs in n_list:               #removes double entries     
        if facs not in fac_list:
            fac_list.append(facs)
    return fac_list

但是对于大n来说这是很耗时的,因为它必须查看所有的数字,而不仅仅是质数。一个素因子列表的组合方法应该快得多。在

编辑:在浏览了几个资源之后,对一个好策略的最好解释是评价最高的答案here on SO。简洁,易于用任何语言实现。案件结案。在


Tags: 方法答案in列表forifnot素数