投影Euler#5（可被1到20的所有数字整除的最小正数）：优化方法~Java语言

Question

问题5:2520是可以被1到10的每个数字除的最小数，没有任何余数。可以被1到20的所有数字整除的最小正数是多少？

我已经解决了Euler项目的问题5

以下是Java代码：

 static long FindLcm(long a,long b)
 {
     long lcm,hcf = 0;
     long i=1;
     long ger=a>b?a:b;
     while(i<ger)
     {
         if((a%i==0) && (b%i==0))
             hcf=i;
         i++;
     }
     lcm=(a*b)/hcf;
     return lcm;
 }
 static void FindMultiple()
 {
     long lcm=1;
     for(long i=2;i<=20;i++)
     {
         lcm=FindLcm(lcm,i);
     }   
     System.out.println("Lcm="+lcm);
 }

如何优化这个？

Answer 1

我就是这样做的，这是我能想到的最简单的方法。它也比你的快一点。

    for(int i = 190; ; i += 190) {
        if(i % 3 == 0 
                && i % 4 == 0
                && i % 6 == 0 
                && i % 7 == 0
                && i % 8 == 0 
                && i % 9 == 0
                && i % 11 == 0
                && i % 12 == 0 
                && i % 13 == 0 
                && i % 14 == 0 
                && i % 15 == 0
                && i % 16 == 0
                && i % 17 == 0
                && i % 18 == 0
                && i % 20 == 0) {
            System.out.println(i);
            break;
        }
    }

Answer 2

你们的解决方案或多或少是蛮力，这就是为什么要花这么长时间。我们知道2520是（1,2，…，9,10）的lcm，这意味着两件有用的事情：1。）我们可以从11和2开始检查系数。）答案是2520的倍数。

您正在搜索答案的最大公约数（gcd）和序列中的下一个数字（类似于气泡排序）。您可以检查当前答案是否可以被下一个因子整除，如果不能，则将当前答案添加到自身，直到答案可以被下一个因子整除。例如：

    static long findLCM(long a, long b) {
        long lcm = (a>b) ? a : b;
        while (lcm % b != 0) {
            lcm += a;
        }
        return lcm;
    }

因为我们从lcm=a开始，我们知道只要我们将a添加到lcm，那么lcm总是可以被a整除。现在，我们只需要使a的一些倍数可以被b整除。这个过程应该省去许多首先找到gcd以及从2到10迭代的步骤。

Answer 3

你的FindMultiple（）方法不错，

static void FindMultiple()
{
    long lcm=1;
    for(long i=2;i<=20;i++)
    {
        lcm=FindLcm(lcm,i);
    }
    System.out.println("Lcm="+lcm);
}

它实现了一个相当好的算法。您的问题是，您的FindLcm（）包含一个严重的性能缺陷。

static long FindLcm(long a,long b)
{
    long lcm,hcf = 0;
    long i=1;
    // This sets ger to max(a,b) - why?
    long ger=a>b?a:b;
    // This would return a wrong result if a == b
    // that never happens here, though
    while(i<ger)
    {
        if((a%i==0) && (b%i==0))
            hcf=i;
        i++;
    }
    lcm=(a*b)/hcf;
    return lcm;
}

您正在循环，直到到达两个参数中较大的一个。由于累积LCM增长相当快，这需要很多时间。但是两个（正）数的GCD（或HCF，如果您愿意）不能大于两个（正）数中较小的一个。因此，仅循环到两个参数中较小的一个为止，使得迭代次数最多为20次，在这里进行19次（对于i=2，...，20），这是一个微不足道的计算量。

更改为

long ger = a < b ? a : b;
while(i <= ger) {

给我（添加计时代码，而不是测量打印）：

17705 nanoseconds
Lcm=232792560

因此计算不到20微秒。如果我们使用欧几里得算法来寻找最大公约数，我们可以很容易地将其推到6微秒以下，

static long gcd(long a, long b) {
    while(b > 0) {
        a %= b;
        if (a == 0) return b;
        b %= a;
    }
    return a;
}

如果我们直接使用GCD作为

lcm *= i/gcd(lcm,i);

在Find多种（）中。