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      20100     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      2080%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      2060      2040      2020      20                 20800 / 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        10080     300        10080     400        100400 % 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        10180     100        102|80     100        400 400 % 80 == 0 && 400 % 100 == 0

     Then 400 is the LCM.