-1

问题：2520 是可以除以 1 到 10 的每个数字而没有余数的最小数字。

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

所以，我试图在项目 euler 上做练习 5，我得出了以下代码：

#include <stdio.h>
#define TRUE 1
#define FALSE 0

int main () {
   int n, fnd = FALSE, count, i; 

   for (i = 1; fnd == FALSE; i++) {       
      count = 0;
      for (n = 1; n <= 20; n++) {
         count += i % n;
      }
      printf ("testing %d, count was: %d\n", i, count);
      if (count == 0) {
         fnd = TRUE;
         printf ("%d\n", i); 
      }
   }
   return 0;
}

我相信我的方法是正确的，它肯定会找到可被 1 到 20 整除的数字。但是它已经计算了 5 分钟，仍然没有结果。我的方法正确吗？如果是，那么还有其他方法吗？我想不出另一种方法来解决这个问题，非常感谢提示。先感谢您。

编辑：所以，根据你们给我的建议，我想通了，非常感谢！所以，它仍然是蛮力，但不是在最后一个数字上加 1，而是现在加 2520，即 1 到 10 的 LCM。因此，计算 2520 的倍数的余数之和是否从 11 到20 是 0。由于 2520 已经可以被 1 整除到 10，所以我只需要除以 11 到 20。

#include <stdio.h>
#define TRUE 1
#define FALSE 0

int main () {
   int n, fnd = FALSE, count, i; 

   for (i = 2520; fnd == FALSE; i = i + 2520) {       
      count = 0;
      for (n = 11; n <= 20; n++) {
         count += i % n;
      }
      printf ("testing %d, count was: %d\n", i, count);
      if (count == 0 && i != 0) {
         fnd = TRUE;
         printf ("%d\n", i); 
      }
   }
   return 0;
}

非常感谢，如果没有你的帮助，我不会解决它 :) PS：它现在计算时间不到 10 秒。

4

7 回答 7

3

您的方法耗时太长，因为它是一种蛮力解决方案。你需要稍微聪明一点。

我给你的提示是：一个数可以被另一个数整除是什么意思？或者低于某个数字的每个数字？数的素因数有共性吗？关于可分性的维基百科页面应该是一个很好的起点。

于 2012-05-06T18:34:21.457 回答
3

提示：您应该查找“最小公倍数”。

下一个提示：

  1. 答案是数字 1、2、3、...、20 的最小公倍数 (LCM)。
  2. n个数的 LCM可以依次找到：如果 LCM(1, 2) = x，则 LCM(1, 2, 3) = LCM( x , 3)；如果 LCM(1, 2, 3) = y，则比 LCM(1, 2, 3, 4) = LCM( y , 4) 等。所以知道如何找到任何 2 个数字的 LCM 就足够了。
  3. 为了找到 2 个数字的 LCM，我们可以使用以下公式：LCM( p , q ) = pq /GCD( p , q )，其中 GCD 是最大公约数
  4. 为了寻找 GCD，有一个著名的 Euclid 算法（也许是地球上第一个非平凡算法）。
于 2012-05-06T18:36:33.070 回答
1

我认为您应该首先计算从 2 到 20 的每个数字的质因数。由于所需的数字应该能被 1 到 20 的每个数字整除，它也必须能被这些数字的每个质因数整除。

此外，重要的是要跟踪主要因素的多样性。例如，4 = 2 * 2，因此所需的数字必须能被 2 * 2 整除。

于 2012-05-06T19:05:56.030 回答
0

我用 Python 3 快速烘焙的东西：

primary_list = []
for i in range(2, 4097):
    j = i
    k = 2
    delta_list = primary_list[0:]
    alpha_list = []
    while j > 1:
        if j % k == 0:
            j /= k
            alpha_list.append(k)
            k = 2
        else:
            k += 1
    for i in alpha_list:
        try:
            delta_list.remove(i)
        except:
            primary_list.append(i)
final_number = 1
for i in primary_list:
    final_number *= i
print(final_number)

这在慢速机器下只需几秒钟即可计算。Python 非常擅长处理抽象数字。工作的最佳工具。

算法比较简单。我们有一个基本列表primary_list，我们在其中存储数字的倍数。然后是我们估计要计算的数字范围的循环。我们使用一个临时变量j作为一个可以轻松除、切和征服的数字。我们使用k作为除数，从2开始。delta_list是 primary_list 的主要工作副本，我们在其中一个接一个地拆分数字，直到只剩下所需的“逻辑”。然后我们将这些数字添加到我们的主要列表中。

1：1
2：2 1
3：3 1
4：2 2 1
5：5 1
6：2 3 1
7：7 1
8：2 2 2 1
9：3 3 1
10：2 5 1

最终数字是通过将我们在primary_list中的数字相乘得到的。
1 * 2 * 3 * 2 * 5 * 7 * 2 * 3 = 2520

如前所述，Python _really_擅长处理数字。这是完成这项工作的最佳工具。这就是为什么你应该使用它而不是 C、Erlang、Go、D 或任何其他动态/静态语言来进行欧拉练习。

于 2012-05-06T19:41:03.310 回答
0

我用C解决了它。下面是算法！

#include <stdio.h>
#include <stdio.h>
int main()
{
 int i;
 int count;
 for(i=21;i>0;i++)
  {  count = 0;
  for( int j=2;j<21;j++)
 {
  if (i%j!=0)
  break;
  count++;
  } 
  if (count==19)
  break;
   }

 printf("%d\n",i);
 return 0;
   }
于 2013-03-09T19:40:03.083 回答
0

只是对以上评论的一些想法，

@pg190 你说“它实际上只需要被 1 到 20 之间的素数整除，即 2、3、5、7、11、13、17、19。” 取 9699690，不偏离 1-20 的所有值。

所以这可能是一个很好的解决方案，

给定数字集 [1-20]

最小公倍数可以如下计算。

前任。对于数字 2,6,9

用素数乘法表示它们 2 2

6 2 3

9 3 3

LCM = 每个素数的最高幂的倍数。= 2*3^2 = 18

这可以通过将每个数字表示为素数乘法然后做这个数学来解决手头的问题。

于 2013-08-18T23:34:28.087 回答
0 
$num=20;
        for($j=19;$j>1;$j--)
        {
            $num= lcm($j,$num);
        }
        echo $num;
        function lcm($num1, $num2)
        {
            $lcm = ($num1*$num2)/(gcd($num1,$num2));
            return $lcm;
        }
        function gcd($n1,$n2)
        {
            $gcd=1;
            $min=$n1;
            if($n1>$n2)
            {
                $min=$n2;
            }
            for($i=$min;$i>1;$i--)
            {
                if($n1%$i==0 && $n2%$i==0)
                {
                    $gcd*=$i;
                    $n1/=$i;
                    $n2/=$i;
                }
            }
            return $gcd;
        }

用php解决

于 2013-09-28T06:45:49.467 回答