c - 为什么我在这里没有得到任何输出？

Question

在 Euler 项目中，有一个名为 Smallest Multiple 的问题。我试图解决它并尝试为该问题编写代码。但是我没有得到任何输出!问题描述如下:

2520 是 1 到 10 中每一个数都可以整除而没有余数的最小数。能被 1 到 20 的所有数字整除的最小正数是多少？

所以我针对这个问题写了代码。首先我写了一个代码来检查2520是可以被1到10的每一个数整除的最小数是否正确。对于这个问题，我编写了以下程序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
  int i,j,count = 0,num;

  for (i = 1; count != 10; i++) {
    count = 0;

    for (j = 1; j <= 10; j++)
      if(!(i % j))
        count++;

    if( count == 10 )
      num = i;
  }

  printf("%d\n",num);
}

我得到了这个问题的理想输出。但是每当我编写这段代码来查找可被 1-20 整除而没有余数的值时，我都找不到任何输出。我写了下面的代码并编译并运行但它没有给我任何结果。但程序仍在运行，每当我按下 Control+C 时，程序就会终止。

问题代码......

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  long long int i,j,count = 0,num;

  for (i = 1; count != 20; i++) {
     count = 0;

     for (j = 1; j <= 20; j++)
       if (!( i % j))
         count++;

     if (count == 20)
       num = i;
  }

  printf("%lld\n",num);
}

那么问题出在哪里呢？

Answer 1

如果我要这样做，我会做一些不同的事情。让我们从考虑一个不是最小的数字开始，但在其他方面显然是正确的，而且非常容易计算:如果你简单地乘以 2 * 3 * 4 * 5 * 6 * ... N，你会得到一个数字可以清楚地被所有这些较小的数字整除。

现在，问题是我们如何生成一个较小 的数字，该数字具有可被所有较小数字整除的相同基本特征。我们可以通过观察(例如)10 个因子到 2 * 2 * 5 来做到这一点，因此(例如)我们不必分别乘以 2、4 或 5 来获得可被 2、4 和5.

因此，我们可以获取我们的数字列表，以及每个数字的质因数分解:

10: 2 * 2 * 5
9:  3 * 3
8:  2 * 2 * 2
7:  7
6:  2 * 3
5:  5
4:  2 * 2
3:  3
2:  2
1:  1

然后我们可以在列表后面的列表中删除出现在列表中较早的因素(但最多与它们在列表中较早出现的次数一样多)。这给了我们这样的东西:

10: 2 * 2 * 5
9:  3 * 3
8:  2
7:  7
6:  -
5:  -
4:  -
3:  -
2:  -

将剩下的 (2 * 2 * 5 * 3 * 3 * 2 * 7) 相乘，得到我们期望的 2520。

对 20 应用相同的技术，我们得到如下列表:20 19 9 17 4 7 13 11。将其相乘，我们得到 232792560。

如果您更关心效率，您可以(例如)使用欧几里得算法来计算一对数字的 GCD。我们在这里计算的是一对数字的 LCM，它是数字除以它们的 GCD 的乘积。然后我们可以重复使用我们之前的 LCM 作为 GCD 的输入之一，所以我们最终得到如下代码:

unsigned LCM = max;

for (int i = max - 1; i > 1; i--)
    LCM = i * LCM / GCD(i, LCM);

还有很多方法可以计算 GCD。一个简单、众所周知且相当有效的算法是 Euclid 算法，它看起来像这样:

unsigned GCD(unsigned u, unsigned v) {
    while ( v != 0) {
        unsigned r = u % v;
        u = v;
        v = r;
    }
    return u;
}

使用它，计算从 5 到 30 的每个 N 的 1..N 的 LCM(并将它们写入文件)在我目前使用的机器上大约需要 3 毫秒(尽管我怀疑更仔细的计时将证明它确实比那更快)。