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.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

The Latest

homes in the real estate industry

Exploring the Latest Tech Trends Impacting the Real Estate Industry

The real estate industry is changing thanks to the newest technological advancements. These new developments — from blockchain and AI to virtual reality and 3D printing — are poised to change how we buy and sell homes. Real estate brokers, buyers, sellers, wholesale real estate professionals, fix and flippers, and beyond may

man on floor with data

DevX Quick Guide to Data Ingestion

One of the biggest trends of the 21st century is the massive surge in internet usage. With major innovations such as smart technology, social media, and online shopping sites, the internet has become an essential part of everyday life for a large portion of the population. Due to this internet

payment via phone

7 Ways Technology Has Changed Traditional Payments

In today’s digital world, technology has changed how we make payments. From contactless cards to mobile wallets, it’s now easier to pay for goods and services without carrying cash or using a checkbook. This article will look at seven of the most significant ways technology has transformed traditional payment methods.