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

攻城狮杰森

发布于 2022-06-03 13:08:23

1.2K0

发布于 2022-06-03 13:08:23

文章被收录于专栏：技术集锦

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 的倍数和为

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

代码实现

暴力求解

/*
 * @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;
}