Project Euler #5(可被 1 到 20 的所有数字整除的最小正数):优化方法?~爪哇 [英] Project Euler #5(Smallest positive number divisible by all numbers from 1 to 20): Ways to Optimize? ~Java

问题描述

问题 5: 2520 是可以除以 1 到 10 中的每个数字而没有任何余数的最小数字.能被 1 到 20 的所有数整除的最小正数是多少?

Problem 5: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

我已经解决了Project Euler

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);
 }

如何优化?

推荐答案

你的FindMultiple()方法还不错，

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

它实现了一个相当好的算法.您的问题是您的 FindLcm() 包含一个令人讨厌的性能错误.

it implements a fairly good algorithm. Your problem is that your FindLcm() contains a nasty performance bug.

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)，这是一个微不足道的数量计算.

You are looping until you reach the larger of the two arguments. Since the cumulative LCMs grow rather fast, that takes a lot of time. But the GCD (or HCF, if you prefer) of two (positive) numbers cannot be larger than the smaller of the two. So looping only until the smaller of the two arguments is reached makes the number of iterations at most 20 here, do that 19 times (for i = 2, ..., 20), it's a trivial amount of computation.

更改为

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

给我(添加时间代码，不测量打印):

gives me (adding timing code, not measuring the printing):

17705 nanoseconds
Lcm=232792560

因此计算时间不到 20 微秒.如果我们使用欧几里德算法找到最大公约数，我们可以轻松地将其推到 6 微秒以下，

So less than 20 microseconds for the computation. We can easily push that below 6 microseconds if we use the euclidean algorithm to find the greatest common divisor,

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

和以下 5 如果我们直接使用 GCD 作为

and below 5 if we directly use the GCD as

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

在FindMultiple()中.

这篇关于Project Euler #5(可被 1 到 20 的所有数字整除的最小正数):优化方法?~爪哇的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！