代码之家  ›  专栏  ›  技术社区  ›  Mr. T Andres Pinzon

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

  •  3
  • Mr. T Andres Pinzon  · 技术社区  · 7 年前

    虽然我看过一些关于寻找素因子和因子的帖子,但我还没有找到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

    1 回复  |  直到 7 年前
        1
  •  3
  •   user448810    7 年前

    您的任务是确定 multiplicative partition 一个数字。谷歌应该告诉你该去哪里。堆栈溢出已存在 an answer .

    推荐文章