Amit Tiwari - 1 year ago 83
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:

``````#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);
}
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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download