Amit Tiwari Amit Tiwari - 4 months ago 42
C Question

Project Euler 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?

My solution:

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)
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.


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).


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.