Finding LCM & GCD in C

Discussion in 'C' started by pradeep, Oct 5, 2005.

  1. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    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;
        }
      }
     
    Last edited: Oct 5, 2005
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    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;
        }
      }
     
  3. SATYAN JANA

    SATYAN JANA New Member

    Joined:
    Jul 31, 2004
    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Programming
    Location:
    Kolkata
    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.
     
  4. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    Right said Satyan, even I was about to post the same.

    Thanks Shabbir for the modified code for the loop.
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Yup realized that.
     
  6. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    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
     
  7. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    thanks buddy.....this might short'n my calcutaion
     
    Last edited by a moderator: Nov 14, 2006
  8. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    BlasterBlang, this is the third time I have been telling you to confine links to signatures only.
     
  9. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
  10. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
    but link are not enable in signatures
     
  11. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    They will appear once on a page. You will see it on the seventh post of the thread.
     
  12. insamd

    insamd New Member

    Joined:
    Dec 18, 2006
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    hey guys,

    Was just interested if with the GCD function if its possible to find the GCD of 3 different numbers rather than just 2? Would be interested to see it.

    Thanks
     
  13. BlasterBlang

    BlasterBlang New Member

    Joined:
    Nov 13, 2006
    Messages:
    10
    Likes Received:
    0
    Trophy Points:
    0
  14. sharma_atul13

    sharma_atul13 New Member

    Joined:
    Jul 16, 2007
    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    liked the way to do manipulations done in LCM and GCD programs
     
  15. clocking

    clocking New Member

    Joined:
    Jun 12, 2007
    Messages:
    122
    Likes Received:
    0
    Trophy Points:
    0
    hi everyone!
    I have code following:
    You see and shift it
    Code:
    struct ths
    {
      char ht[24];
      char tt[21];
      int sobd;
      float m,l,;
    };
    class ts
    {
       private:
        int sots;
        ths *ts;
      public:
       ts()
       {
        sots = 0 ;
        ts = NULL;
       }
    void swap();
    };
    
    void ts::swap()
    {
      int n = sots;
      for ( int i = 1; i < n; ++i)
      for (int j = i + 1; j <= n; ++j)
      if (ts[i].m < ts[j].m)
      {
         ths tmp = ts[i];
         ts[i] = ts[j];
         ts[j] = tg;
      }
    }
    // thanks.
     
    Last edited by a moderator: Jul 22, 2007
  16. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    [COMMENT]Use code tag ([ code][/code ]) when you have code snippets in the post.[/COMMENT]
     
  17. clocking

    clocking New Member

    Joined:
    Jun 12, 2007
    Messages:
    122
    Likes Received:
    0
    Trophy Points:
    0
    :) Thanks so much, my friend!
    this is code in C++, how do you see ?
    ofcourse, Class in C++ is difficult.
    What way do you help me to express easy?
     
  18. clocking

    clocking New Member

    Joined:
    Jun 12, 2007
    Messages:
    122
    Likes Received:
    0
    Trophy Points:
    0
    hi everybody!
    Follow you, Can we do in swap 2 structs easier?
    Code:
    tmp = ts[i] ;
    ts[i] = ts[j];
    ts[j] = tmp;
    
    thanks.
     
  19. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    You can swap the struct if they are addresses and not the objects can be done in that way unless they have the overloaded = operator.
     
  20. clocking

    clocking New Member

    Joined:
    Jun 12, 2007
    Messages:
    122
    Likes Received:
    0
    Trophy Points:
    0
    thank, but can we do easier for it ?
    not tmp.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice