Problem 5:Least evenly divisible number

Q. 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 number that is evenly divisible by all of the numbers from 1 to 20 ?

Sol:

It can be easily seen that the question is asking the LCM of the numbers.The problem can be solved without even resorting to algorithms.Just compute the prime factorization of numbers and multiply the highest power of each prime.

20 = 2^2 * 5
19 = 19
18 = 2 * 3^2
17 = 17
16 = 2^4
15 = 3 * 5
14 = 2 * 7
13 = 13
11 = 11 

Since all the lesser numbers have been included, they can be safely ignored..

And

lcm= 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

Now, the problem seems so simple, but what if we were to calculate the result for natural numbers from 1 to an arbitrary number(say ' n ').

It can be observed that 

LCM(a,b,c,d)=LCM(b,c,LCM(a,d))

To implement it, we can run a loop from 2 to n-1 and at each step find the lcm of loop variable and the previous stage lcm.The lcm can be easily found by applying euclid's algorithm of finding GCD as

 LCM(a,b)=(a*b)/GCD(a,b).

Now the coding part:

int main()

{

scanf("%d",&lastnumber);

long n=20;

 for(i=2;i < 20; i++)

 {

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

 }

 printf(" %ld \n", n);

return 0;

}

The euclid's algo can be implemented as:

int gcd(int a,int b)

{

    if(a == 0)

       return b;

    while(b != 0)

        if (a > b)

           a = a - b;

        else

           b = b - a;

    return a;

}

Thats all it is to the problem :D

Please post your comments and doubts...
Suggestion for better algorithms are always welcome.....