【欧拉计划第 1 题】3 或 5 的倍数 Multiples of 3 or 5

2022-06-07 285

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【欧拉计划第 1 题】3 或 5 的倍数 Multiples of 3 or 5

Problem 1 Multiples of 3 or 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

问题 1 3 或 5 的倍数

如果我们列出所有小于 10 且是 3 或 5 的倍数的自然数，我们会得到 3、5、6 和 9。这些倍数之和是 23。

求 1000 以下所有 3 或 5 的倍数之和。

思路分析

暴力求解

常规思路，找到 1000 以内所有 3 或 5 的倍数，分别求和解决

优化思路

由于暴力解法的算法执行效率很低，需要重复遍历 1000 次，自然效率低下。我们只需要枚举 3 的倍数之和、5 的倍数之和，最后减去它们的最小公倍数之和，便可节省不少时间

1000 以内 k 的倍数和为

( 1000 − 1 ) k \large \frac{\left (1000-1 \right)}{k}k(1000−1)

代码实现

暴力求解

/*
 * @Author: coder-jason
 * @Date: 2022-04-04 22:59:48
 * @LastEditTime: 2022-04-04 23:00:56
 */
#include <iostream>
using namespace std;
int main()
{
   int sum = 0;
   for (int i = 0; i < 1000;i++){
         if (i % 3 == 0 || i % 5 == 0){
              sum += i;
         }
   }
   cout<<sum<<endl;
   return 0;
}

优化思路

/*
 * @Author: coder-jason
 * @Date: 2022-04-04 22:59:48
 * @LastEditTime: 2022-04-04 23:14:34
 */
#include <iostream>
using namespace std;
int calculate()
{
      int sum3 = 0, sum5 = 0, sum15 = 0;
      for (int i = 0; i <= (1000 - 1) / 3; i++)
      {
            sum3 += i * 3; //求出3的倍数的和
      }
      for (int i = 0; i <= (1000 - 1) / 5; i++)
      {
            sum5 += i * 5; //求出5的倍数的和
      }
      for (int i = 0; i <= (1000 - 1) / 15; i++)
      {
            sum15 += i * 15; //求出15的倍数的和
      }
      return sum3 + sum5 - sum15;
}
int main()
{
      cout << calculate();
      return 0;
}