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: