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