Go4Expert

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

pradeep 6Oct2005 01:18

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.

pradeep 6Oct2005 13:34

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.

pradeep 7Oct2005 11:08

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 02:10.