Project Euler第一题Java代码时间复杂度优化求助

题目描述 #

若列出所有小于10且为3或5的倍数的自然数，可得到3、5、6、9，这些倍数的和为23。
请计算所有小于1000且为3或5的倍数的自然数之和。

原可运行代码 #

public class Sum {
    private static final int n = 1000; 
    
    public static void main(String[] args) {
        for (int i = 1, sum = 0; i <= n; i++) {
            if ((i % 3 == 0) || (i % 5 == 0)) {
                 System.out.println(sum += i);
            }   
        }
    }
}

原代码存在的问题 #

• 时间复杂度为O(n)，需要遍历1到n的所有数字做取模判断，当n取值很大时执行效率极低
• 边界逻辑有误：题目要求计算小于1000的数，原代码循环条件为i <= n，会把1000（5的倍数）计入结果，导致答案错误
• 循环内每次累加都执行打印操作，产生大量无意义IO开销

O(1)复杂度优化方案 #

用数学容斥原理+等差数列求和直接计算，不需要遍历：

1. 核心逻辑：所有3或5的倍数之和 = 3的倍数之和 + 5的倍数之和 - 15的倍数之和（同时是3、5倍数的数被重复加了两次，需要减去一次）
2. 小于上限limit的k的倍数天然构成等差数列，用等差数列求和公式可以直接算出和：
   • 项数p = (limit - 1) // k （即小于limit的最大k的倍数除以k的商）
   • 倍数和 = k * p * (p + 1) / 2

优化后代码：

public class Sum {
    private static final int LIMIT = 1000;

    private static long calcMultipleSum(int k, int limit) {
        long count = (limit - 1) / k;
        return k * count * (count + 1) / 2;
    }

    public static void main(String[] args) {
        long result = calcMultipleSum(3, LIMIT) + calcMultipleSum(5, LIMIT) - calcMultipleSum(15, LIMIT);
        System.out.println(result);
    }
}

运行后得到正确结果233168。
这个优化方案不管上限取多大，都只需要固定3次求和计算，哪怕上限是百亿级也能瞬间得出结果，性能远高于遍历写法。

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