We need to write a program that will determine what is the greatest common divisor of two dissimilar numbers. There are two main problems here: user input and the algorithm itself.
We’ll need to ask the user to input two numbers, but the two numbers cannot be the same. In order to prevent this we could use an if statement to warn the user if the numbers aren’t the same. We’ll need to store those numbers somewhere too:
#include<iostream>
int main()
{
int a;
int b;
std::cout << "Type in number 1: ";
std::cin >> a;
std::cout << std::endl;
std::cout << "Type in number 2: ";
std::cin >> b;
std::cout << std::endl;
if (a == b)
{
std::cout << "Type in two numbers that are not the same."
<< std::endl;
}
return 0;
}The problem we’re facing here now is that the program will only run once and not do anything other than printing a warning when user types in the same numbers. We’ll need to use a loop that’ll run until user types in two dissimilar numbers. Let’s use a while loop.
#include<iostream>
int main()
{
int a;
int b;
while (a == b)
{
std::cout << "Type in number 1: ";
std::cin >> a;
std::cout << std::endl;
std::cout << "Type in number 2: ";
std::cin >> b;
std::cout << std::endl;
if (a == b)
{
std::cout << "Type in two numbers that are not the same."
<< std::endl;
}
}Now onto the actual algorithm itself. We need to find the greatest common divisor of two numbers. The greatest common divisor is the greatest number that’ll divide two numbers into an integer (e.g. without a decimal point). Let’s have a look at a table of two numbers 12 & 24:
| Quotient A (for A =24) | Quotient B (for B = 12) | Divisor |
| 24 | 12 | 1 |
| 12 | 6 | 2 |
| 4 | 2 | 6 |
| 2 | 1 | 12 |
| `1 | – | 24 |
As we can see from the table above the greatest common divisor for numbers 12 and 24 is 12, which means that the GDC will be lesser than or equal to the lower number of the pair.. Let’s see if we can find them using a program.
We could have a loop that’ll divide the numbers by an integer. We’ll divide them until we reach the lower number of the pair:
#include<iostream>
int main()
{
int a;
int b;
int loopBound;
while (a == b)
{
std::cout << "Type in number 1: ";
std::cin >> a;
std::cout << std::endl;
std::cout << "Type in number 2: ";
std::cin >> b;
std::cout << std::endl;
if (a == b)
{
std::cout << "Type in two numbers that are not the same."
<< std::endl;
}
}
for (int i = 1; i < loopBound; i++)
{
}
return 0;
}Since the loop boundary must be the lower of the two, we’ll need to make sure that the program is aware of it. Let’s use an if statement to check and correctly determine which one is the lower one.
#include<iostream>
int main()
{
int a;
int b;
int loopBound;
while (a == b)
{
std::cout << "Type in number 1: ";
std::cin >> a;
std::cout << std::endl;
std::cout << "Type in number 2: ";
std::cin >> b;
std::cout << std::endl;
if (a == b)
{
std::cout << "Type in two numbers that are not the same."
<< std::endl;
}
}
if (a < b)
{
loopBound = b;
}
else
{
loopBound = a;
}
for (int i = 1; i < loopBound; i++)
{
}
return 0;
}We’ll now start dividing. We’re only interested in the quotients that have a remainder equal to 0. Let’s use an if statement to capture that:
#include<iostream>
int main()
{
int a;
int b;
int loopBound;
int GCD = 1;
while (a == b)
{
std::cout << "Type in number 1: ";
std::cin >> a;
std::cout << std::endl;
std::cout << "Type in number 2: ";
std::cin >> b;
std::cout << std::endl;
if (a == b)
{
std::cout << "Type in two numbers that are not the same."
<< std::endl;
}
}
if (a < b)
{
loopBound = b;
}
else
{
loopBound = a;
}
for (int i = 1; i < loopBound; i++)
{
if (a % i == 0)
{
if (b % i == 0)
{
GCD = i;
}
}
}
return 0;
}The if statement above first checks the first number inputted by the user and determines whether its reminder divided by the current value of ‘i’ (which starts at 1) has a remainder equal to 0. If it doesn’t then it discards the number and moves on to the next iteration. If it does then it’ll check whether the second number also has a remainder equal to 0 when divided by the current ‘i’. If that’s true then it’ll update the value of GCD with the current i, otherwise it’ll discard the number and the loop will iterate again until it finds the greatest common divisor. And that’s the whole program.