Go4Expert
Page 1 of 6
1
2
3
Last »
Show 40 post(s) from this thread on one page

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forumdisplay.php?f=60)
-   -   Finding LCM & GCD in C (http://www.go4expert.com/showthread.php?t=457)

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 06:41.
Page 1 of 6
1
2
3
Last »
Show 40 post(s) from this thread on one page