dcsimg
Login | Register   
LinkedIn
Google+
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

By submitting your information, you agree that devx.com may send you DevX offers via email, phone and text message, as well as email offers about other products and services that DevX believes may be of interest to you. DevX will process your information in accordance with the Quinstreet Privacy Policy.


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

WEBINAR:

On-Demand

Building the Right Environment to Support AI, Machine Learning and Deep Learning


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
Thanks for your registration, follow us on our social networks to keep up-to-date