Euclidean Algorithm implementation written in C++.

Subtraction-based version:

Iteration version:

// © 2017 TheFlyingKeyboard
// theflyingkeyboard.net

#include <iostream>

using namespace std;

int gcd(int a, int b);

int main(){
  int num1;
  int num2;
  
  cout << "Enter first number: ";
  cin >> num1;
  
  cout << "Enter second number: ";
  cin >> num2;
  
  cout << "GCD of " << num1 << " and " << num2 << " is equal to " << gcd(num1, num2) << endl;
  
  return 0;
}

int gcd(int a, int b){
  while(a != b){
    if(a > b){
      a = a - b;
    }else{
      b = b - a;
    }
  }
  
  return a;
}

Recursive version:

// © 2017 TheFlyingKeyboard
// theflyingkeyboard.net

#include <iostream>

using namespace std;

int gcd(int a, int b);

int main(){
  int num1;
  int num2;
  
  cout << "Enter first number: ";
  cin >> num1;
  
  cout << "Enter second number: ";
  cin >> num2;
  
  cout << "GCD of " << num1 << " and " << num2 << " is equal to " << gcd(num1, num2) << endl;
  
  return 0;
}

int gcd(int a, int b){
  if(a > b){
    return gcd(a - b, b);
  }else if(a < b){
    return gcd(a, b - a);
  }else{
    return a;
  } 
}

Division-based version:

Iteration version:

// © 2017 TheFlyingKeyboard
// theflyingkeyboard.net

#include <iostream>

using namespace std;

int gcd(int a, int b);

int main(){
  int num1;
  int num2;
  
  cout << "Enter first number: ";
  cin >> num1;
  
  cout << "Enter second number: ";
  cin >> num2;
  
  cout << "GCD of " << num1 << " and " << num2 << " is equal to " << gcd(num1, num2) << endl;
  
  return 0;
}

int gcd(int a, int b){
  int t;
  
  while(b != 0){
    t = b;
    b = a % b;
    a = t;
  }
  
  return a;
}

Recursive version:

// © 2017 TheFlyingKeyboard
// theflyingkeyboard.net

#include <iostream>

using namespace std;

int gcd(int a, int b);

int main(){
  int num1;
  int num2;
  
  cout << "Enter first number: ";
  cin >> num1;
  
  cout << "Enter second number: ";
  cin >> num2;
  
  cout << "GCD of " << num1 << " and " << num2 << " is equal to " << gcd(num1, num2) << endl;
  
  return 0;
}

int gcd(int a, int b){
  if(b == 0){
    return a;
  }
  else{
    return gcd(b, a % b);
  }
}

 

C++ Euclidean Algorithm
Tagged on:     

Leave a Reply

Your email address will not be published. Required fields are marked *