001.3或5的倍数

题目:

如果我们将小于10的所有是3或5倍数的自然数列出来,我们得到3,5,6和9,它们的和是23。与之类似,计算1000以下所有是3或5的倍数的自然数的和。

想法1:

第一种思路就是通过i % 3 == 0 || i % 5 == 0这个表达式筛选出所有符合要求的数,然后进行依次相加即可。这个算法的时间复杂度为O(n);

代码实现:

#include<iostream>
using namespace std;

int main() {
int ans = 0;
for (int i = 0; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
ans += i;
}
}
cout << ans << endl;
return 0;

想法2:

第二种想法就是求出3的倍数和,再求出5的倍数和,然后进行相加。由于在相加过程中会重复相加3和5的最小公倍数,所以我们还得减去3和5的最小公倍数15的倍数和。对于求这三个数的倍数和问题,我们可以用等差数列进行求解.这个算法的时间复杂度为O(1);

代码实现:

#include<iostream>
using namespace std;

int main() {
/*int ans = 0;
for (int i = 0; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
ans += i;
}
}*/
int t3 = (3 + 999) * 333 / 2;
int t5 = (5 + 995) *199/ 2;
int t15 = (15 + 990) * 66 / 2;
cout << t3+t5-t15 << endl;
return 0;
}

原文地址:https://www.cnblogs.com/liyaning/p/14726439.html