  Advertiser Disclosure
 TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK Specialized Dev Zones Research Center eBook Library .NET Java C++ Web Dev Architecture Database Security Open Source Enterprise Mobile Special Reports 10-Minute Solutions DevXtra Blogs Slideshow    Home » Tip Bank » .NET » VB.NET » Math Processing
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 Submit a Tip Browse ".NET" Tips Browse All Tips   Comment and Contribute

(Maximum characters: 1200). You have 1200 characters left.    Thanks for your registration, follow us on our social networks to keep up-to-date