求满足条件的小于1400的数的个数：X可表为自身6个因数之和

首先明确问题：寻找小于1400的数X，使得X可以表示为其6个不同的真因数之和（真因数指除X自身外的正因数）。若允许重复使用因数，解法会有所不同，下文将分别说明。

核心思路 #

1. 真因数获取：对每个X，先找出所有真因数。
2. 动态规划验证：使用动态规划判断是否存在6个不同的真因数之和等于X，避免暴力枚举所有组合（效率极低）。

代码实现（不同真因数情况） #

def get_proper_divisors(x):
    divisors = set()
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            divisors.add(i)
            counterpart = x // i
            if counterpart != x:
                divisors.add(counterpart)
    return sorted(divisors)

def has_six_distinct_divisors_sum(x):
    divs = get_proper_divisors(x)
    # 真因数数量不足6个，直接排除
    if len(divs) < 6:
        return False
    
    # DP表：dp[k][s] 表示用k个不同真因数能否得到和s
    dp = [[False] * (x + 1) for _ in range(7)]
    dp[0][0] = True  # 初始状态：0个因数和为0
    
    for d in divs:
        # 逆序遍历，避免重复使用同一个因数
        for k in range(5, -1, -1):
            for s in range(x, d - 1, -1):
                if dp[k][s - d]:
                    dp[k + 1][s] = True
                    # 提前终止：找到符合条件的组合
                    if k + 1 == 6 and s == x:
                        return True
    return dp[6][x]

# 统计符合条件的数
count = 0
solutions = []
for x in range(1, 1400):
    if has_six_distinct_divisors_sum(x):
        count += 1
        solutions.append(x)

print(f"小于1400且满足条件的数共有 {count} 个")
print("这些数为:", solutions)

代码说明 #

• get_proper_divisors：通过遍历到√X高效获取所有真因数，避免重复。
• has_six_distinct_divisors_sum：使用动态规划，逆序更新状态确保每个因数只被使用一次，一旦找到符合条件的组合立即返回，提升效率。

允许重复因数的情况 #

若允许重复使用因数，只需修改动态规划的更新逻辑（正序遍历），代码如下：

def has_six_divisors_sum_with_repeats(x):
    divs = get_proper_divisors(x)
    if not divs:
        return False
    
    dp = [[False] * (x + 1) for _ in range(7)]
    dp[0][0] = True
    
    for k in range(1, 7):
        for s in range(x + 1):
            for d in divs:
                if s >= d and dp[k-1][s - d]:
                    dp[k][s] = True
                    break
            if dp[k][x]:
                return True
    return dp[6][x]

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