1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

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,646
    Likes Received:
    86
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    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,283
    Likes Received:
    364
    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,646
    Likes Received:
    86
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    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,283
    Likes Received:
    364
    Trophy Points:
    83
    Yup realized that.
     
  6. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,646
    Likes Received:
    86
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    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,283
    Likes Received:
    364
    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,283
    Likes Received:
    364
    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,283
    Likes Received:
    364
    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,283
    Likes Received:
    364
    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