Project Euler #5(Smallest positive number divisible by all numbers from 1 to 20): Ways to Optimize? ~Java

Question

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?

I have solved the problem 5 of Project Euler

Here is the Java code:

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

How can optimize this?

Answer 1

Your FindMultiple() method is not bad,

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

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

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.

Changing to

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

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

17705 nanoseconds
Lcm=232792560

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

and below 5 if we directly use the GCD as

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

in FindMultiple().