C++ program to implement Euclidean algorithm to find GCD of two number














































C++ program to implement Euclidean algorithm to find GCD of two number



/* C++ program to implement euclidean algorithm to find greatest common divisor of two numbers
* GCD of numbers a , b equals a if b is 0
* GCD of numbers a , b equals b if a is 0
* GCD of numbers a , b is same as GCD of numbers b , a % b
* Time complexity of algorithm is O(log(min(a,b)))
*/

#include <iostream>
using namespace std;
template<typename T>
inline T gcd(T a, T b) {
T c;
while (b) {
c = b;
b = a % b;
a = c;
}
return a;
}
int main() {
int a = 12;
int b = 20;
cout << "gcd of " << a << " and " << b << " is: " << gcd(a, b) << '\n';
a =
12;
b =
0;
cout << "gcd of " << a << " and " << b << " is: " << gcd(a, b) << '\n';
a =
0;
b =
0;
cout << "gcd of " << a << " and " << b << " is: " << gcd(a, b) << '\n';
return 0;
}

Output of above program is:

Comments