devxlogo

Find Common Denominators in C++

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

devxblackblue

About Our Editorial Process

At DevX, we’re dedicated to tech entrepreneurship. Our team closely follows industry shifts, new products, AI breakthroughs, technology trends, and funding announcements. Articles undergo thorough editing to ensure accuracy and clarity, reflecting DevX’s style and supporting entrepreneurs in the tech sphere.

See our full editorial policy.

About Our Journalist