Amit Tiwari - 9 months ago 59

C Question

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?

My solution:

`#include<stdio.h>`

int gcd(int m, int n);

int lcm(int a, int b);

int main()

{

int x=1, i;

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

{

x=lcm(x, i+1);

}

printf("The answer is:\t%d", x);

return 0;

}

int gcd(int m, int n)

{

while(m!=n)

{

if(m>n)

m=m-n;

else

n=n-m;

}

return m;

}

int lcm(int a, int b)

{

return ((a*b)/gcd(a, b));

}

Please tell where I am wrong? It shows only blank screen on running.

Answer

If there should be only one lesson that you learn from this exercise, make it this: **the order in which you do your multiplications and divisions matters**.

Even if it does not matter in mathematics, it often matters in your program. For example, in math there is no difference between `(a*b)/gcd(a, b)`

and `a/gcd(a, b)*b`

; In your program, it would make the difference between passing and failing.

(P.S. of course you need to fix the bug in your logic, too: you should not be multiplying `x`

by lcm).

**EDIT**

To understand why the order makes the difference here, consider calculating `lcm`

of `232792560`

and `20`

. `232792560`

is divisible by `20`

, so it is the `lcm`

. However, when you calculate `232792560*20`

, you get an overflow; then you divide by `20`

, but you do not get `232792560`

back.

Since the divisor is `gcd(a,b)`

, you can divide it out of `a`

before multiplying by `b`

without truncating the result by integer division. This little trick that experienced programmers use without thinking can save you hours of debugging.

Source (Stackoverflow)