Greatest common divisor

I wrote a program to find the greatest common divisor between two numbers. How do I improve this program?

#include<iostream>
using namespace std;

int main() {

int first_number;
cout<<"Enter First Number : ";
cin>>first_number;

if(first_number < 0)
cout << "Please enter a positive number" << endl;
cin >> first_number;

int  second_number;
cout<<"Enter Second Number: ";
cin>>second_number;

if(second_number < 0)
cout << "Please enter a positive number" << endl;
cin >> second_number;

int  gcd;
for(int i=1;i<=first_number&&i<=second_number;i++){

if(first_number%i==0 && second_number%i == 0 ){

gcd=i;

}

}

cout<<"Greatest Common Divison (GCD):"<<gcd<<endl;
return 0;
}

• btw C++ now has a builtin std::gcd – Aryaman Jun 20 '18 at 22:08

A more elegant implementation of the gcd function:

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}


To ensure that the arguments are positive, it's easiest to use the abs(...) function.

And put spaces around operators. For example, instead of this:

for(int i=1;i<=first_number&&i<=second_number;i++){


Write like this:

for (int i = 1; i <= first_number &&i <= second_number; i++) {


Putting it together, the implementation of the entire program can become short and sweet:

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

int main() {
int num1, num2;

cout << "Enter first number: ";
cin >> num1;
cout << "Enter second number: ";
cin >> num2;

cout << "Greatest Common Divisor: " << gcd(abs(num1), abs(num2)) << endl;
}


You can play with this on ideone.

1. Stop using using namespace std. Read this

2. It seems like you don't want users inputting negative numbers. If a user does, he's prompted to enter again. What if the user inputs a negative number again? You need to use a while loop here, or just have your program change the input to positive.

//Check if user input is negative.
num1 = (num1 > 0) ? num1 : -num1;
num2 = (num2 > 0) ? num2 : -num2;

3. I think using recursion will help. Have a look at this question

This is how I would implement Euclid's algorithm. (Might need it's own review):

#include <iostream>
#include <functional>

using std::cin;
using std::cout;
using std::endl;
using std::function;

int main() {

//Wrapped lambda expression. You can create a function that does the same thing.
function<int(int,int)> gcd = [&](int m, int n){
if(m<n) return gcd(n,m);
int remainder(m%n);
if(0 == remainder) return n;
return gcd(n,remainder);
};

int num1,num2;

cout << "Enter first number: ";
cin >> num1;
cout << "Enter second number: ";
cin >> num2;

//Check if user input is negative.
num1 = (num1 > 0) ? num1 : -num1;
num2 = (num2 > 0) ? num2 : -num2;

cout << "Greatest Common Divisor: " << gcd(num1,num2) << endl;

}

• Umm... where hcf is defined? – vnp Oct 15 '14 at 6:40
• @vnp oops, edited. I was thinking of highest common factor. – Quaxton Hale Oct 15 '14 at 6:47
• Why not using unsigned int when you don't want to allow negative numbers? – Markus Mayer Oct 15 '14 at 6:54
• Yeah I know what hcf stands for. Успехов. – vnp Oct 15 '14 at 6:57
• @MarkusMayer I don't think that will work. If the input is negative, it will be converted to UINT_MAX + 1 + num. – Quaxton Hale Oct 15 '14 at 7:08

Firstly, as this is meant to be for code reviews, I will immediately point out that you are putting everything into main and you really should put the algorithm into its own function. Your main can look at its argument list and possibly support having the parameters in there. For simplistic terms you can use them if they are there and prompt if not.

For an implementation of the function, it can be a simple free-function. There is no need to use a class for it.

int gcd( int x, int y )
{
if( x < y )
return gcd( y, x );

int f = x % y;
if( f == 0 )
return y;
else
return gcd( y, f );
}


without recursion

 int gcd( int x, int y )
{
if( x < y )
std::swap( x, y );

while( y > 0 )
{
int f = x % y;
x = y;
y = f;
}
return x;
}


For a simple example, gcd of 987 and 1491

x takes the greater value so:
x = 1491
y = 987
f (mod) = 504

next iteration
x = 987
y = 504
f (mod) = 483

next iteration:
x = 504
y = 483
f (mod) = 21

next iteration
x = 483
y = 21
f( mod ) = 0

final:
x = 21
y = 0

return 21


The complexity of this algorithm: well the worst case scenario is actually 2 consecutive Fibonacci numbers. The answer will be 1 but if this is the nth and (n+1)th Fibonacci number it will take n iterations to unravel.

Thus it's O(log N) complexity where N is the higher of the two numbers.

I'm going to address your original algorithm, as I think that there are some useful lessons that can be learned there. Note that EngieOP's algorithm is going to be faster than this though.

When doing something like this, think about the direction that you want the for loop to go. You want the greatest common divisor, but your for loop starts with the smallest possible divisor. Turn it around and go in the other direction.

Also note that you know that the greatest common divisor is going to be at most the smaller of the two numbers. So calculate the smaller number.

for ( int divisor = std::min(first_number, second_number); divisor > 0; divisor-- ) {
if ( 0 == first_number % divisor && 0 == second_number % divisor ) {
cout << "Greatest Common Divisor (GCD):  " << divisor << endl;
}
}


Note how we can stop as soon as we find the first match because we went largest to smallest. This saves us loop iterations, a variable declaration, and an if statement.

• Using std::min() would greatly improve the readability of your for loop. – Markus Mayer Oct 15 '14 at 6:52
• I'd consider getting rid of those yoda conditions. – Pharap Apr 22 '17 at 7:42

First and foremost, you don't want to write a program to calculate gcd. You want to write a function to calculate it, and a program to test the function. Don't put everything in main.

Second, Euclid spelled out the algorithm really well; there's (almost) no point to deviate from it unless you are seriously into the number theory; check out a Stein's approach.