Problem
Given two non-negative integers a and b, you’ve to find the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of the two numbers. In other words, find the largest number that divides them both.
Euclidean Algorithm
The Euclidean algorithm is one of the oldest numerical algorithms to compute the greatest common divisor (gcd) of two positive integers.
Euclidean Using subtraction
GCD (a, b) 1. if a==0: 2. return b 3. while b != 0: 4. if (a>b) 5. a = a-b 6. else 7. b = b-a 8. return a
Time Complexity: O(n) where n = a+b
Euclidean Using division
GCD (a, b) 1. if b == 0: 2. return a 3. else 4. return GCD (b, a mod b);
Time Complexity: O(log(n)) where n = a+b
Code Implementation
//
// main.cpp
// GCD
//
// Created by Himanshu on 19/09/21.
//
#include <iostream>
using namespace std;
int gcdUsingSubtarction (int a, int b) {
if (a == 0) {
return b;
}
while (b != 0) {
if (a>b)
a = a - b;
else
b = b - a;
}
return a;
}
int gcdUsingDivision (int a, int b) {
if (b == 0) {
return a;
} else {
return gcdUsingDivision (b, a%b);
}
}
int main() {
int a = 7, b = 43;
printf("GCD of %d and %d using subtraction is %d \n", a, b, gcdUsingSubtarction(a, b));
printf("GCD of %d and %d using division is %d \n", a, b, gcdUsingDivision(a, b));
a = 21;
b = 343;
printf("GCD of %d and %d using subtraction is %d \n", a, b, gcdUsingSubtarction(a, b));
printf("GCD of %d and %d using division is %d \n", a, b, gcdUsingDivision(a, b));
return 0;
}
Output
GCD of 7 and 43 using subtraction is 1 GCD of 7 and 43 using division is 1 GCD of 21 and 343 using subtraction is 7 GCD of 21 and 343 using division is 7
Here’s a working example: Ideone
Practice problem
Solution (You should try to solve this problem yourself first) – CodeChef