Find Common Denominators in C++

   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
   }

   x    y
-------------
  80  100
 100   20
  20    0

• 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.

   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)
   }
     

x       y        prod     GCD(x)
---------------------------------
80     100        800     
80      20
60      20
40      20
20      20                 20

800 / 20 = 400

• 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.