题目链接：3或5的倍数

解法一：暴力枚举

C语言代码

1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
int main (){
    int sum = 0;
    for(int i = 0;i<1000;i++){
        if(i%3==0 || i%5==0)
            sum +=i;
    }
    printf("%d\n",sum);
    return 0;
}
//运行结果：233168

上面这个解法的时间复杂度为O（N），因为数据量小，所以可以使用暴力。
但如果把题目的1000变成$1000^{10000}$那么暴力解法的运行时间将非常高，因为需要枚举的数量会呈指数级增长。

Java代码

1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 0; i < 1000; i++) {
            if (i % 3 == 0 || i % 5 == 0) {
                sum += i;
            }
        }
        System.out.println(sum);
    }
}

解法二：容斥原理

容斥原理常用于解决包含多个集合的计数问题，其基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果 既无遗漏又无重复。

本题，我们假设3的倍数的集合叫做集合A，5的倍数的集合叫做集合B。根据容斥原理，我们需要计算集合A和集合B的交集，既是3的倍数又是5的倍数的个数。
所以，根据容斥原理，我们可以使用以下公式计算交集的大小：$|A ∩ B| = |A| + |B| - |A ∪ B|$

知道了这些，这道题就简单了。接下来，我们需要计算小于1000的自然数中所有3或5的倍数的和。
3或5的倍数的和 = 3的倍数的和 + 5的倍数的和 - 15的倍数的和

求1000以内3或5或15的倍数的和，可以使用等差数列求和公式：$S=\frac{1}{2} n\left ( a_{1}+ a_{n}\right )$
C语言代码

1
2
3
4
5
6
7
8
#include<stdio.h>
int main (){
    int sum3 = (3+999/3*3)*(999/3)/2;
    int sum5 = (5+999/5*5)*(999/5)/2;
    int sum15 = (15+999/15*15)*(999/15)/2;
    printf("%d\n",sum3+sum5-sum15);
    return 0;
}

Java代码

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        int sum3 = (3 + (999 / 3) * 3) * (999 / 3) / 2;
        int sum5 = (5 + (999 / 5) * 5) * (999 / 5) / 2;
        int sum15 = (15 + (999 / 15) * 15) * (999 / 15) / 2;
        int result = sum3 + sum5 - sum15;
        System.out.println(result);
    }
}