Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: C++
Expertise: Beginner
Jan 23, 2007

Find Common Denominators in C++

The functions in this tip find the greatest common divisor (GCD) or the least common multiple (LCM) of two given integers.

  1. Getting the GCD through recursion:
    
       int GCD(int x,int y)
       {
          if(y==0)  // base case, the programs stops if y reaches 0.
             return x;     //it returns the GCD
          else 
            return GCD(y,x%y); //if y doesn't reach 0 then recursion continues
       }
    
    Suppose x=80 and y=100:
    
       x    y
    -------------
      80  100
     100   20
      20    0
    
    The GCD function shown above returns 20 as the GCD of the two given integers.
  2. Getting the GCD through iteration:

    • Using the While Loop:
      
         int GCD(int x,int y)
         {
            int t;       
            while (y!=0)
            {
               t=y;
               y=x%y;
               x=t;
            }
            return x;
         }
      
      Suppose x=80 and y=100:
      
      x       y        t 
      -----------------------
       80    100      20
      100     20       0            
       20      0  
      
      Then x=20 and the GCD of 80 and 100 is 20.
    • Using the For Loop:
      
         int GCD(int x,int y)
         {
            int i;
            if(x<y)
            {
               for(i=x;i>=0;i--)
               {
                  if(x%i==0 &&y%i==0)
                     {return i;}
               }
            }
            else
            {
               for(i=y;i>=0;i--)
               {
                  if(x%i==0 && y%i==0)
                     {return i;}
               }
            }
            return i;
         }
      
      Suppose x=80 and y=100:
      
      x       y        i 
      -----------------------
       80    100      79
       80    100      78
       80    100      77
      |
       80    100      20
      
      80%20==0 && 100%20==0
      
      Then 20 is the GCD.
  3. Getting the LCM through recursion:
    
       int LCM(int x,int y)
       {
          int prod;
          if(y%x==0)
             return y;
          else
          {
             prod=x*y;
             while(x!=y) // get the GCD of 2 given integers
             {
                if(x>y)
                   x=x-y;
                else
                   y=y-x;   //x now is the GCD
             }
             return LCM(y,prod/x);  //recurse, changing x to y and vice versa
          }   //LCM = (x*y)/(GCD)
       }
         
    
    Suppose x=80 and y=100:
    
    x       y        prod     GCD(x)
    ---------------------------------
    80     100        800     
    80      20
    60      20
    40      20
    20      20                 20
    
    800 / 20 = 400
    
    Therefore, the LCM is 400.
  4. Getting LCM through iteration:

    • Using the While Loop:
      
         int LCM(int x,int y)
         {
            int i;
            i=y;
            while(y%x!=0)
               y=y+i;
            return y;
         }
      
      Suppose x=80 and y=100:
      
      x       y          i    
      ------------------------
      80     100        100     
      80     200        100
      80     300        100
      80     400        100
      
      400 % 80 = 0
      
      Then 400 is the LCM.
    • Using the For Loop:
      
         int LCM(int x,int y)
         {
            int i;
            if (x>ly)
               for(i=x;i<=x*y;i++)
               {
                  if (i%x==0 && i%y==0)
                     return i;
               }
            else
               for(i=y;i<=x*y;i++)
               {
                  if (i%x==0 && i%y==0)
                     return i;
               }
            return i;
         }      
      
      Suppose x=80 and y=100:
      
      x       y          i    
      ------------------------
      80     100        100     
      80     100        101
      80     100        102
      |
      80     100        400 
      
      400 % 80 == 0 && 400 % 100 == 0
      
      Then 400 is the LCM.
Sherman Guanlao
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap