Page 1 of 6123>Last » Show 40 post(s) from this thread on one page

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Finding LCM & GCD in C (http://www.go4expert.com/articles/finding-lcm-gcd-c-t457/)

Finding LCM & GCD in C

Two of my friends faced a problem with writing a program which finds the LCM(Lowest Common Multiple)/GCD(Greatest Common Divisor) of two positive integers, so I helped them out by writing two functions for each. I thought many others might be having the same problem.
So here are the functions:

For LCM:
Code:

```/* a & b are the numbers whose LCM is to be found */   int lcm(int a,int b)   {     int n;     for(n=1;;n++)     {           if(n%a == 0 && n%b == 0)             return n;     }   }```
For GCD:
Code:

```/* a & b are the numbers whose GCD is to be found.  Given a > b  */   int gcd(int a,int b)   {     int c;     while(1)     {           c = a%b;           if(c==0)             return b;           a = b;           b = c;     }   }```

 shabbir 6Oct2005 03:51

Re: Finding LCM & GCD in C

For LCM
Code:

`if(n%a == 0 && n%b == 0)`
shouldn't this be
Code:

`if(a%n == 0 && b%n == 0)`
Also just another way to write the loop
Code:

```    for(n=1;;n++)     {           if(n%a == 0 && n%b == 0)             return n;     }```
can be
Code:

```for(n=1;a%n == 0 && b%n == 0;n++); return n```
For GCD Given a > b can be avoided if we have the following code
Code:

```  int gcd(int a,int b)   {     int c;     if(a<b)     {         c = a;         a = b;         b = c;     }     while(1)     {           c = a%b;           if(c==0)             return b;           a = b;           b = c;     }   }```

 SATYAN JANA 6Oct2005 12:55

Re: Finding LCM & GCD in C

Shabbir,
Least Common Multiple(L.C.M.) of 'a' and 'b' is the smallest number 'n' which is both perfectly divisible by 'a' as well as 'b'; i.e. n%a == 0 && n%b == 0.

Re: Finding LCM & GCD in C

Right said Satyan, even I was about to post the same.

Thanks Shabbir for the modified code for the loop.

 shabbir 6Oct2005 13:55

Re: Finding LCM & GCD in C

Quote:
 Originally Posted by SATYAN JANA Shabbir, Least Common Multiple(L.C.M.) of 'a' and 'b' is the smallest number 'n' which is both perfectly divisible by 'a' as well as 'b'; i.e. n%a == 0 && n%b == 0.
Yup realized that.

Re: Finding LCM & GCD in C

Quote:
 Also just another way to write the loop Code: for(n=1;;n++) { if(n%a == 0 && n%b == 0) return n; } can be Code: for(n=1;a%n == 0 && b%n == 0;n++); return n
This loop won't work, the condition given would prevent the execution even once.
The correct code would be:
Code:

```  for(n=1;n%a != 0 && n%b != 0;n++);   return n```

 BlasterBlang 14Nov2006 17:55

Re: Finding LCM & GCD in C

thanks buddy.....this might short'n my calcutaion

 shabbir 14Nov2006 18:17

Re: Finding LCM & GCD in C

BlasterBlang, this is the third time I have been telling you to confine links to signatures only.

 BlasterBlang 17Nov2006 16:43

Re: Finding LCM & GCD in C

ok...fine

 BlasterBlang 17Nov2006 16:45

Re: Finding LCM & GCD in C

but link are not enable in signatures

 All times are GMT +5.5. The time now is 21:05. Page 1 of 6123>Last » Show 40 post(s) from this thread on one page