Finding LCM & GCD in C

pradeep's Avatar author of Finding LCM & GCD in C
This is an article on Finding LCM & GCD in C 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;
    }
  }
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
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;
    }
  }
0
SATYAN JANA's Avatar
Light Poster
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.
0
pradeep's Avatar, Join Date: Apr 2005
Team Leader
Right said Satyan, even I was about to post the same.

Thanks Shabbir for the modified code for the loop.
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
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.
0
pradeep's Avatar, Join Date: Apr 2005
Team Leader
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
0
BlasterBlang's Avatar, Join Date: Nov 2006
Go4Expert Member
thanks buddy.....this might short'n my calcutaion

Last edited by shabbir; 14Nov2006 at 18:17.. Reason: Confine links to signatures only
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
BlasterBlang, this is the third time I have been telling you to confine links to signatures only.
0
BlasterBlang's Avatar, Join Date: Nov 2006
Go4Expert Member
ok...fine
0
BlasterBlang's Avatar, Join Date: Nov 2006
Go4Expert Member
but link are not enable in signatures