java - Project Euler #5(可被 1 到 20 的所有数字整除的最小正数): Ways to Optimize? ~Java

Question

习题5:2520是能被1到10的每一个数整除而没有余数的最小数。能被 1 到 20 的所有数字整除的最小正数是多少？

我已经解决了Project 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

你的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 作为 5 以下

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

在 FindMultiple() 中。