求质数列表中乘积为目标数的质数组合（时间复杂度O(√n)）

问题描述 #

给定质数列表：

lst = [2,3,5,7]

num = 40

需要得到质数组合[2,2,2,5]，使其乘积为40，要求算法时间复杂度最大为O(√n)。

已完成步骤 #

• 编写函数遍历((num ** 0.5) + 1)范围并返回对应列表；
• 编写质数判断函数；
• 编写函数筛选出步骤1返回列表中的质数；
• 主函数遇到瓶颈：不知道如何遍历列表生成所有可能的质数组合（如[2,2,2,2]、[2,2,2,3]等），并找到乘积为40的组合。考虑过递归，但不确定是否能维持**O(√n)**的时间复杂度，也不清楚具体实现方式。

限制说明 #

注：该问题可通过迭代器/生成器解决，但尚未学习generator（Yield）或迭代器相关知识，因此无法使用此类方法，现有生成器解法不符合要求。

补充信息 #

我会处理已知列表的组合生成，例如以下代码可生成从AAA到CCC的所有组合：

def ABC(num,tempComb,new_list):
    if num == 0:    
        new_list.append(temp_combi)
        return new_list
    lst = ["A","B","C"]
    take_1=ABC(num-1,tempComb+[lst[0]],new_list)
    take_2=ABC(num-1,tempComb+[lst[1]],new_list)
    take_3=ABC(num-1,tempComb+[lst[2]],new_list)
    return take_1 + take_2 + take_3

但面对未知长度的列表时，不知道如何实现类似的组合生成逻辑。

更新：可行解法 #

该问题的英文名为Prime factorization（质因数分解），以下为满足要求的可行代码：

def prime_components(num): # 40
    i = 2
    factors = []
    while i <= num:
        if (num % i) == 0:
            factors.append(i)
            num = num / i
        else:    
            i = i + 1
    return factors

内容的提问来源于stack exchange，提问作者LearningToCode