项目Euler #5

Question

在C++中，我有一个关于Project Euler Task5的问题，它是: 2520是一个最小的数字，可以被从1到10中的每个数字除以，没有任何余数。

能被从1到20的所有数字整除的最小正数是多少？

我已经写了代码，我认为它应该可以工作，但它不能……老实说，我不知道为什么它不能，所以任何帮助都会非常感谢：

#include <iostream>

using namespace std;

int main()
{
  int smallestprod = 1;

  for (int ii = 1; ii <= 20; ii++)
    {
      if (smallestprod % ii != 0)
        smallestprod *= ii;
    }

  cout << "The integer you are looking for is: " << smallestprod << "\n";
  system("pause");
}

我试着通过放置循环来检查我的工作：

for (int jj = 1; jj <= 20; jj++)
  {
    cout << smallestprod % jj << "\n";
  }

我希望输出全为0(对于循环的jj部分)，这是由于我的ii for循环中的逻辑，但我得到了一些非零数，这导致我得到了错误的答案……我已经在这个问题上胡闹了一段时间了，真的不明白ii for循环中的逻辑在哪里螺丝up...help？

Answer 1

我认为你得到的数字太大了，而且将一个通常不是质数的变量称为“最小质数”也是令人困惑的。

手动跟踪循环：

i=1; smallestprime = 1
i=2; smallestprime = 1 * 2
i=3; smallestprime = 2 * 3
i=4; smallestprime = 6 * 4

但在最后一步中，你只需要乘以2，以确保你的答案可以被4整除。(12是可被1，2，3，4整除的最小数字，而不是24)。

我认为如果你尝试一些手动的例子，比如手动计算2520数字，它会变得更清楚该怎么做。基本上，当您循环遍历整数k以累积答案N时，您需要乘以k的一些素数因子的子集-仅足以使N可被k整除，但仅此而已。

可能最有效的方法是使用LCM和GCD之间的关系，并使用欧几里德算法计算LCM。

Answer 2

我会把你的代码分成多个方法，每个方法都解决自己的问题。如前所述，最大公约数是计算最小公倍数的基础，因此

int greatestCommonDivisor(int a, int b)
{
}

两个数字的LCM是

int greatestCommonDivisor(int a, int b)
{
}

似乎只需在循环中调用greatestCommonDivisor(int，int )就可以解决数字数组的LCM问题：

int leastCommonMultiple(int[] nums, int len)
{
    int curr = 1;
    for(int i = len-1; i >= 0; --i) {
        curr = leastCommonMultiple(curr, nums[i]);
    }
    return curr;
}

Answer 3

将从1到20的所有数字相乘时，标准32位整数将会溢出，最大值仅为2147 483 647。因此，不可能在int变量中存储这样的乘法结果，这就是您在输出中发现“奇怪”效果的原因。

但是你并不需要把所有的数字从1到20相乘才能得到答案。找出在给定范围内出现的所有主要因素及其重数就足以解决问题。