Greatest common divisor

Question

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;
}

Answer 1

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.

---

Please also indent your code nicely to make it more readable.

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.

Answer 2

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;
   
   }
   

Answer 3

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.

Answer 4

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.

Answer 5

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.

The rest is well addressed in the answers above.