如何高效统计区间[start, end]内仅含3或5为质因数的数字数量？

你的原代码思路没问题，但如果end - start的量级很大（比如超过1e8），逐个遍历判断的方法肯定会超时——因为时间复杂度是O(n)，n是区间长度，10秒根本跑不完这么多循环。

换个思路：这类数本质是仅由3和5的幂次相乘得到的数（形如3^a * 5^b，其中a、b是≥0的整数，且不同时为0，因为1不能被3或5整除）。我们可以直接生成所有符合条件且不超过end的数，再统计其中落在[start, end]区间内的数量。

实现步骤 #

• 生成所有3的幂次，对每个3的幂次，再乘以所有可能的5的幂次，得到所有组合数
• 用集合去重（避免重复生成同一个数，比如35和53是同一个数）
• 统计集合中落在目标区间内且不等于1的数的个数

示例代码 #

def count_valid_numbers(start, end):
    valid_nums = set()
    # 生成所有3的幂次
    power_3 = 1
    while power_3 <= end:
        # 基于当前3的幂次，生成所有3^a *5^b的组合
        power_5 = 1
        current = power_3 * power_5
        while current <= end:
            valid_nums.add(current)
            power_5 *= 5
        power_3 *= 3
    # 统计区间内符合要求的数（排除1，因为1不能被3或5整除）
    return sum(1 for num in valid_nums if start <= num <= end and num != 1)

为什么这个方法高效？ #

因为3和5的幂次增长极快，比如当end是1e12时：

• 3的幂次最多只有25个（3^{25≈8.47e11，3}26就超过1e12了）
• 5的幂次最多只有16个（5^{16≈1.52e11，5}17超过1e12）
• 总组合数也就25*16=400个左右，生成和统计的时间可以忽略不计，完全不会触发超时。

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