Finding LCM & GCD in C

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

  1. oleber

    oleber New Member

    Joined:
    Apr 23, 2007
    Messages:
    37
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Software Developer (Perl, C/C++ and Java)
    Location:
    Hamburg, Germany
    Home Page:
    http://oleber.freehostia.com/
    Lets see the performance.

    :confused: Which is the fastest algorithm?

    :) GCM seems to be at most n
    :( LCM seems to be at most n*m

    :p so, if you do lcm(a,b) := (a*b)/gcm(a,b), you get a n complexity

    :eek: This is mathematics.
     
  2. oleber

    oleber New Member

    Joined:
    Apr 23, 2007
    Messages:
    37
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Software Developer (Perl, C/C++ and Java)
    Location:
    Hamburg, Germany
    Home Page:
    http://oleber.freehostia.com/
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  4. oleber

    oleber New Member

    Joined:
    Apr 23, 2007
    Messages:
    37
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Software Developer (Perl, C/C++ and Java)
    Location:
    Hamburg, Germany
    Home Page:
    http://oleber.freehostia.com/
    clocking and shabbir are speaking of swaping variables.

    This subject was already spoken in the other thread. Just that
     
  5. clocking

    clocking New Member

    Joined:
    Jun 12, 2007
    Messages:
    122
    Likes Received:
    0
    Trophy Points:
    0
    :) hi !
    thanks for your idea. But I only want someone tell me about that algorithm.
    Swapping is not difficult, but I'm interested in the easier way solving it.
    Code:
    tmp = ts[i];
    ts[i] = ts[j];
    ts[j] = tmp;
    
    can't we use tmp ?
     
  6. Balaselvi

    Balaselvi New Member

    Joined:
    Dec 18, 2007
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Hi,

    This is Bala.
    I want to know how to calculate GCD of many numbers, ex 2048 values.

    Please help.

    Thanks in advance.
     
  7. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Code:
    int main()
    {
        int n1,n2,n3,n;
        cout<<" Numbers are : ";
        cin>>n1>>n2>>n3;
        n=FindGcd(FindGcd(n1,n2),n3);
        cout<<"GCD of n1,n2,and n3 is "<<n<<endl;
        return 0;
    }
    
    int FindGcd(int num1, int num2)
    {
        int temp;    
        while(num2!=0)
        {
            temp = num2;
            num2 = num1%num2; 
            num1 = temp;
        }     
        return num1;
    }
     
    Last edited by a moderator: Feb 27, 2008
  8. aisha.ansari84

    aisha.ansari84 New Member

    Joined:
    Feb 13, 2008
    Messages:
    82
    Likes Received:
    1
    Trophy Points:
    0
    can you please tell me when the loop will actually stop
     
  9. zeeme

    zeeme New Member

    Joined:
    Feb 22, 2009
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    correct code is this 100% checked!

    for(n=1;n%a != 0 || n%b != 0;n++);
    return n
     
  10. vanishing_stapler

    vanishing_stapler New Member

    Joined:
    May 14, 2009
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    When I searched for lcm c++, this thread had the top two spots, so I figured that I'd join and put this here.

    For finding the LCM (Least Common Multiple) of two integers, a and b, in C++, use:

    for(n=a;n%b != 0;n+=a);
    return n;

    For maximum speed, try to set it up so that the larger number is "a" and the smaller one is "b".

    The reasoning:
    The least common multiple (LCM) of two numbers, a and b, is the smallest number that is a multiple of "a" AND a multiple of "b". If we already know that the LCM is a multiple of "a", then why not count by "a"? When we count by "a", starting at "a", we are testing every number that is a multiple of "a" already, and only have to see if it is a multiple of "b" too. This code does just that. When "a", the number we're counting by, is larger than 1, the process will be much faster than with those other suggestions, because it's taking bigger steps (at the same speed per step) to get to the same solution.

    If "a" is a billion, then this will be at least a billion times faster than this:

    for(n=1;n%a != 0 || n%b != 0;n++);
    return n;

    (even though both work)

    I hope this helps.
     
  11. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    For lcm try this one:
    int lcm(int a,int b)
    {
    int n;
    if(a<b)
    {
    n=a;
    a=b;
    b=n;
    }
    for(n=a;n%b!=0;n+=a)
    return n;
    }:happy:
     
  12. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    After 8 posts I would have thought you would know about code blocks by now. USE THEM PLEASE.
     
  13. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    For lcm try this one:
    Code:
    int lcm(int a;int b)
    {
                 int n;
                 if(a<b)
                 {
                             n=a;
                             a=b;
                             b=n;      
                 }
                 for(n=a;n%b!=0;n+=a)
                      return n;
    } 
    :happy:
     
  14. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    i had written that function using blocks.i don't know what happened when i posted it.
     
  15. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Added that for you now.
     
  16. jackspa

    jackspa New Member

    Joined:
    Feb 20, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
  17. Zaiber

    Zaiber New Member

    Joined:
    Dec 16, 2009
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Actually, I used the code on the first page to correct my code 'til I got it right. Needed this for a take home exam for C class.

    Thanks, and in return I'll give you my code which might help someone.

    Code:
    int gcd( int x, int y) {
             if ( y == 0 ) {
             return x;
             }
              else if (x%y == 0) {
              return y;
              }
              else {
               return gcd(y,x%y);
              }
              }
     
  18. COKEDUDE

    COKEDUDE New Member

    Joined:
    Feb 17, 2010
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Wouldn't this code also cover both cases of GCD whether your first variable is bigger or your second variable is bigger?

    Code:
    void gcd(int x, int y)
    {
        if (x > y)
        {
            int c;
            while(1)
            {
                c = x % y;
                return y;
                x = y;
                y = c;
            }
        if (y > x)
        {
            int d;
            while(1)
            {
                d = x % y;
                return x;
                y = x;
                x = d;
            }
    
        }
    }
     
  19. Zaiber

    Zaiber New Member

    Joined:
    Dec 16, 2009
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Mine worked for both instances ok.
     
  20. COKEDUDE

    COKEDUDE New Member

    Joined:
    Feb 17, 2010
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Wow your code is so much simpler and easier to use :). Thx for the code. I'm just stubborn about making up my own stuff sometimes.
     

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