项目Euler#5(最小的正数除以1到20之间的所有数字):优化方法？〜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().