咨询：如何实现输入n输出所有和为n的质数组合的程序？

需求：编写程序，从输入获取数字n，输出所有和为n的质数组合，输出需按字典序排列。
示例：输入n=13时，输出如下：

2 2 2 2 2 3
2 2 2 2 5
2 2 2 7
2 2 3 3 3
2 3 3 5
2 11
3 3 7
3 5 5
13

目前我已实现1到n之间质数的查找，但不知道如何扩展生成符合要求的组合，现有代码如下：

n = int(input())
lst = []
for i in range(2, n + 1):
    isPrime = True
    for j in range(2, i - 1):
        if i % j == 0:
            isPrime = False
    if isPrime:
        lst.append(i)

print(lst)

请求指导完成完整程序开发。

解决步骤 #

1. 优化质数判断逻辑

你当前的质数判断效率较低，且存在冗余遍历。优化后的逻辑只需遍历到目标数的平方根（若存在大于平方根的因数，必然对应一个更小的因数）：

def is_prime(num):
    if num < 2:
        return False
    for j in range(2, int(num**0.5) + 1):
        if num % j == 0:
            return False
    return True

def get_primes(n):
    return [i for i in range(2, n+1) if is_prime(i)]

2. 用回溯法生成非递减质数组合

要保证输出按字典序排列，组合中的质数必须是非递减的（避免出现3 2这类逆序组合）。通过回溯时限制下一个选择的质数不小于当前组合的最后一个质数，既能避免重复组合，又自然满足字典序要求。

完整代码：

def is_prime(num):
    if num < 2:
        return False
    for j in range(2, int(num**0.5) + 1):
        if num % j == 0:
            return False
    return True

def get_primes(n):
    return [i for i in range(2, n+1) if is_prime(i)]

def find_prime_combinations(n):
    primes = get_primes(n)
    result = []
    
    def backtrack(remaining, current_comb, start_idx):
        if remaining == 0:
            result.append(current_comb.copy())
            return
        if remaining < 0:
            return
        
        for i in range(start_idx, len(primes)):
            prime = primes[i]
            if prime > remaining:
                break  # 质数大于剩余和，后续质数更大，直接跳过
            current_comb.append(prime)
            backtrack(remaining - prime, current_comb, i)  # 从当前索引开始选，保证非递减
            current_comb.pop()
    
    backtrack(n, [], 0)
    return result

# 主程序
n = int(input())
combinations = find_prime_combinations(n)
for comb in combinations:
    print(' '.join(map(str, comb)))

代码说明

• 质数预生成：一次性生成所有不大于n的质数，避免重复判断。
• 回溯逻辑：
  • 当剩余和为0时，当前组合符合要求，加入结果列表。
  • 从start_idx开始遍历质数，确保组合始终非递减，输出时自动满足字典序。
  • 若当前质数大于剩余和，直接终止遍历（质数列表递增，后续质数不可能凑出剩余和）。

测试输入13时，输出完全匹配示例要求。

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