质数列表幂集计算性能优化求助：大数值场景执行过慢

原代码的性能瓶颈在于先生成所有r≥2的质数组合再计算乘积，大量组合的乘积早就超过目标值number，完全属于无效计算，而且重复计算乘积的开销极大。下面是针对性的优化方案：

核心优化思路：迭代剪枝+复用中间结果 #

我们不需要生成所有组合，而是逐步构建乘积，一旦乘积超过number就立即停止后续扩展，同时复用已计算的乘积结果，避免重复运算。

优化后的完整代码 #

import math

number = 200
p1 = []
# 生成指定数值以下的所有质数（原逻辑优化：提前终止循环）
for i in range(2, number + 1):
    is_prime = True
    sqrt_i = math.isqrt(i)
    for prime in p1:
        if prime > sqrt_i:
            break  # 超过平方根无因数，直接判定为质数
        if i % prime == 0:
            is_prime = False
            break
    if is_prime:
        p1.append(i)

Pp = []
# 迭代生成所有乘积≤number的质数组合（r≥2）
# 用栈保存当前乘积和对应的质数索引，确保组合不重复
current_stack = [(prime, idx) for idx, prime in enumerate(p1)]

while current_stack:
    current_prod, current_idx = current_stack.pop()
    # 只遍历当前质数之后的元素，避免重复组合（如2*3和3*2）
    for next_idx in range(current_idx + 1, len(p1)):
        next_prime = p1[next_idx]
        new_prod = current_prod * next_prime
        if new_prod > number:
            continue  # 乘积超限，直接剪枝
        Pp.append(new_prod)
        # 将新的乘积和索引入栈，继续扩展更长的组合
        current_stack.append((new_prod, next_idx))

# 可选：排序（质数组合的乘积理论上唯一，按需执行）
Pp = sorted(Pp)
print(Pp)

优化细节说明 #

1. 提前剪枝：只要新乘积超过number，就跳过后续扩展，彻底避免无效计算
2. 复用中间结果：基于已有的乘积（如23=6）继续乘以后续质数（65=30），无需重新计算整个组合的乘积
3. 避免重复组合：通过索引控制只乘当前质数之后的元素，确保每个组合仅生成一次，减少冗余
4. 内存高效：无需存储所有组合，仅维护当前有效的中间乘积，内存占用远低于原代码

质数生成的小优化 #

原质数生成逻辑可以通过平方根判断和提前break减少循环次数：当遍历的质数超过当前数的平方根时，即可判定为质数，无需继续循环。

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