求指定范围内能被3或5整除的数的和：优化低效代码需求

原代码通过遍历每个数判断是否能被3或5整除来累加求和，这种方法在处理**大数（比如10^9级别）**时会因为循环次数过多导致严重的时间延迟，时间复杂度为O(n)。我们可以用数学公式直接计算，把时间复杂度降到O(1)，彻底解决性能问题。

核心思路 #

利用等差数列求和公式：

• 能被3整除的数的总和：sum3 = 3 * k * (k + 1) / 2，其中k = num // 3（num以内能被3整除的数的个数）
• 能被5整除的数的总和：sum5 = 5 * m * (m + 1) / 2，其中m = num // 5
• 能被15整除的数的总和（因为这些数被同时算进了sum3和sum5，需要去重）：sum15 = 15 * p * (p + 1) / 2，其中p = num // 15

最终总和 = sum3 + sum5 - sum15

优化后的代码 #

#include <stdio.h>

int main() {
    long long num;
    long long sum = 0;
    
    scanf("%lld", &num);
    
    long long k = num / 3;
    long long sum3 = 3 * k * (k + 1) / 2;
    
    long long m = num / 5;
    long long sum5 = 5 * m * (m + 1) / 2;
    
    long long p = num / 15;
    long long sum15 = 15 * p * (p + 1) / 2;
    
    sum = sum3 + sum5 - sum15;
    
    printf("%lld", sum);
    return 0;
}

关键注意点 #

• 使用long long类型：当num很大时，计算出的总和会远超32位int的最大值（约2^31-1），必须用64位整数类型避免溢出。
• 无循环计算：直接通过公式推导结果，无论num多大都能瞬间得到答案，完全消除循环带来的时间消耗。

内容的提问来源于stack exchange，提问作者AMEER KHAN B