There are several approaches to finding the Greatest Common Divisor (GCD) of two numbers

There are several approaches to finding the Greatest Common Divisor (GCD) of two numbers.

Here are some of the commonly used approaches:

Euclidean Algorithm: This is the most popular and efficient method for finding the GCD of two numbers. The algorithm works by repeatedly subtracting the smaller number from the larger number until both numbers are equal. At this point, the GCD is the common value. The algorithm can also be implemented using the modulo operation, which makes it even faster.

#include <iostream>
using namespace std;

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

int main() {
    int num1, num2;
    cout << "Enter two numbers to find their GCD: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "GCD of " << num1 << " and " << num2 << " is " << result << endl;
    return 0;
}

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
result = gcd(num1, num2)
print(f"GCD of {num1} and {num2} is {result}")

The gcd function takes two integer arguments a and b and returns their GCD. If b is 0, then a is the GCD, so we return a. Otherwise, we call the gcd function recursively with arguments b and a % b. This continues until b becomes 0, at which point we return a. In the main function, we get the two numbers from the user, call the gcd function, and print the result.

Prime Factorization: This approach involves finding the prime factors of the two numbers and then finding the common factors. The GCD is then obtained by multiplying all the common factors together. This approach is slower than the Euclidean algorithm for large numbers.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> primeFactors(int num) {
    vector<int> factors;
    for (int i = 2; i * i <= num; i++) {
        while (num % i == 0) {
            factors.push_back(i);
            num /= i;
        }
    }
    if (num > 1) {
        factors.push_back(num);
    }
    return factors;
}

int gcd(int num1, int num2) {
    vector<int> factors1 = primeFactors(num1);
    vector<int> factors2 = primeFactors(num2);
    vector<int> commonFactors;
    for (int factor : factors1) {
        if (find(factors2.begin(), factors2.end(), factor) != factors2.end()) {
            commonFactors.push_back(factor);
            factors2.erase(find(factors2.begin(), factors2.end(), factor));
        }
    }
    int result = 1;
    for (int factor : commonFactors) {
        result *= factor;
    }
    return result;
}

int main() {
    int num1, num2;
    cout << "Enter two numbers to find their GCD: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "GCD of " << num1 << " and " << num2 << " is " << result << endl;
    return 0;
}

def primeFactors(num):
    factors = []
    i = 2
    while i * i <= num:
        while num % i == 0:
            factors.append(i)
            num //= i
        i += 1
    if num > 1:
        factors.append(num)
    return factors

def gcd(num1, num2):
    factors1 = primeFactors(num1)
    factors2 = primeFactors(num2)
    commonFactors = []
    for factor in factors1:
        if factor in factors2:
            commonFactors.append(factor)
            factors2.remove(factor)
    result = 1
    for factor in commonFactors:
        result *= factor
    return result

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
result = gcd(num1, num2)
print(f"GCD of {num1} and {num2} is {result}")

The primeFactors function takes an integer argument num and returns a vector (or list in Python) of prime factors of num. The function uses a while loop to check for prime factors starting from 2 up to the square root of num. If num is divisible by the current factor, then the factor is added to the vector and num is divided by the factor. This process is repeated until num is no longer divisible by the factor. If num is greater than 1 after the loop, then num itself is a prime factor and is added to the vector.

The gcd function takes two integer arguments num1 and num2 and returns their GCD using the Prime Factorization approach. The function calls primeFactors on both num1 and num2 to get their prime factors. It then finds the common factors between the two vectors of prime factors by iterating over the factors in factors1 and checking if they are in factors2. If a common factor is found, it is added to

**Binary GCD Algorithm: **This is a faster version of the Euclidean algorithm that uses bitwise operations instead of division and multiplication. It works by dividing both numbers by 2 until both are odd, then subtracting the smaller odd number from the larger odd number. This process is repeated until both numbers are equal, and the GCD is the common value.

#include <iostream>
using namespace std;

int gcd(int num1, int num2) {
    if (num1 == num2) {
        return num1;
    }
    if (num1 == 0) {
        return num2;
    }
    if (num2 == 0) {
        return num1;
    }
    if ((num1 & 1) == 0) {
        if ((num2 & 1) == 0) {
            return gcd(num1 >> 1, num2 >> 1) << 1;
        } else {
            return gcd(num1 >> 1, num2);
        }
    } else {
        if ((num2 & 1) == 0) {
            return gcd(num1, num2 >> 1);
        } else {
            if (num1 > num2) {
                return gcd((num1 - num2) >> 1, num2);
            } else {
                return gcd((num2 - num1) >> 1, num1);
            }
        }
    }
}

int main() {
    int num1, num2;
    cout << "Enter two numbers to find their GCD: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "GCD of " << num1 << " and " << num2 << " is " << result << endl;
    return 0;
}

def gcd(num1, num2):
    if num1 == num2:
        return num1
    if num1 == 0:
        return num2
    if num2 == 0:
        return num1
    if (num1 & 1) == 0:
        if (num2 & 1) == 0:
            return gcd(num1 >> 1, num2 >> 1) << 1
        else:
            return gcd(num1 >> 1, num2)
    else:
        if (num2 & 1) == 0:
            return gcd(num1, num2 >> 1)
        else:
            if num1 > num2:
                return gcd((num1 - num2) >> 1, num2)
            else:
                return gcd((num2 - num1) >> 1, num1)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
result = gcd(num1, num2)
print(f"GCD of {num1} and {num2} is {result}")

The gcd function takes two integer arguments num1 and num2 and returns their GCD using the Binary GCD Algorithm. The function starts by handling some special cases: if num1 and num2 are equal, then the GCD is num1 (or num2); if either num1 or num2 is 0, then the GCD is the other number.

The function then uses bitwise operations to determine if num1 and num2 are even or odd. If both are even, then the GCD is twice the GCD of their half values. If one is even and the other is odd, then the function calls itself recursively with the even number divided by 2. If both are odd, then the function subtracts the smaller from the larger and calls itself recursively with the result and the smaller odd number divided by

Division Algorithm: This approach involves dividing the larger number by the smaller number and taking the remainder. If the remainder is zero, then the smaller number is the GCD. If not, the smaller number becomes the divisor, and the remainder becomes the dividend. This process is repeated until the remainder is zero.

#include <iostream>
using namespace std;

int gcd(int num1, int num2) {
    while (num2 != 0) {
        int temp = num2;
        num2 = num1 % num2;
        num1 = temp;
    }
    return num1;
}

int main() {
    int num1, num2;
    cout << "Enter two numbers to find their GCD: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "GCD of " << num1 << " and " << num2 << " is " << result << endl;
    return 0;
}

def gcd(num1, num2):
    while num2 != 0:
        temp = num2
        num2 = num1 % num2
        num1 = temp
    return num1

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
result = gcd(num1, num2)
print(f"GCD of {num1} and {num2} is {result}")

The gcd function takes two integer arguments num1 and num2 and returns their GCD using the Division Algorithm. The function uses a while loop to repeatedly divide the larger number by the smaller number and update the values of num1 and num2 until num2 becomes 0. At this point, num1 is the GCD and is returned by the function.

**Extended Euclidean Algorithm: ** This algorithm not only finds the GCD of two numbers, but also the coefficients x and y such that ax + by = gcd(a, b). This algorithm is useful for solving certain types of linear Diophantine equations. The algorithm uses the same basic idea as the Euclidean algorithm, but keeps track of the coefficients x and y at each step.

#include <iostream>
using namespace std;

void extendedGcd(int num1, int num2, int& gcd, int& x, int& y) {
    if (num1 == 0) {
        gcd = num2;
        x = 0;
        y = 1;
        return;
    }
    int x1, y1;
    extendedGcd(num2 % num1, num1, gcd, x1, y1);
    x = y1 - (num2 / num1) * x1;
    y = x1;
}

int main() {
    int num1, num2, gcd, x, y;
    cout << "Enter two numbers to find their GCD and coefficients: ";
    cin >> num1 >> num2;
    extendedGcd(num1, num2, gcd, x, y);
    cout << "GCD of " << num1 << " and " << num2 << " is " << gcd << endl;
    cout << "Coefficients x and y for ax + by = gcd(a, b): " << x << " " << y << endl;
    return 0;
}

def extended_gcd(num1, num2):
    if num1 == 0:
        return num2, 0, 1
    gcd, x1, y1 = extended_gcd(num2 % num1, num1)
    x = y1 - (num2 // num1) * x1
    y = x1
    return gcd, x, y

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
gcd, x, y = extended_gcd(num1, num2)
print(f"GCD of {num1} and {num2} is {gcd}")
print(f"Coefficients x and y for ax + by = gcd(a, b): {x} {y}")

The extendedGcd or extended_gcd function takes two integer arguments num1 and num2 and returns their GCD and coefficients x and y such that ax + by = gcd(a, b). The function first checks if num1 is 0 and returns num2, 0, 1 if true. Otherwise, it recursively calls itself with num2 % num1 and num1 as arguments and gets the GCD and coefficients x1 and y1. Finally, it calculates the coefficients x and y using x = y1 - (num2 / num1) * x1 and y = x1. The GCD and coefficients are returned by the function.

Recursive Algorithm: This approach involves writing a recursive function that calls itself with smaller inputs until the base case is reached. The base case is when one of the inputs is zero, in which case the other input is the GCD.

#include <iostream>
using namespace std;

int gcd(int num1, int num2) {
    if (num2 == 0)
        return num1;
    return gcd(num2, num1 % num2);
}

int main() {
    int num1, num2;
    cout << "Enter two numbers to find their GCD: ";
    cin >> num1 >> num2;
    cout << "GCD of " << num1 << " and " << num2 << " is " << gcd(num1, num2) << endl;
    return 0;
}

def gcd(num1, num2):
    if num2 == 0:
        return num1
    return gcd(num2, num1 % num2)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"GCD of {num1} and {num2} is {gcd(num1, num2)}")

The gcd function takes two integer arguments num1 and num2 and returns their GCD. The function checks if num2 is 0 and returns num1 if true. Otherwise, it recursively calls itself with num2 and num1 % num2 as arguments and returns the result. The GCD is printed in the main function.

The differences between the approaches

1. Euclidean Algorithm: This is the most popular and efficient method for finding the GCD of two numbers. The algorithm works by repeatedly subtracting the smaller number from the larger number until both numbers are equal. At this point, the GCD is the common value. The algorithm can also be implemented using the modulo operation, which makes it even faster.
2. Prime Factorization: This approach involves finding the prime factors of the two numbers and then finding the common factors. The GCD is then obtained by multiplying all the common factors together. This approach is slower than the Euclidean algorithm for large numbers.
3. Binary GCD Algorithm: This is a faster version of the Euclidean algorithm that uses bitwise operations instead of division and multiplication. It works by dividing both numbers by 2 until both are odd, then subtracting the smaller odd number from the larger odd number. This process is repeated until both numbers are equal, and the GCD is the common value.
4. Division Algorithm: This approach involves dividing the larger number by the smaller number and taking the remainder. If the remainder is zero, then the smaller number is the GCD. If not, the smaller number becomes the divisor, and the remainder becomes the dividend. This process is repeated until the remainder is zero.
5. Extended Euclidean Algorithm: This algorithm not only finds the GCD of two numbers, but also the coefficients x and y such that ax + by = gcd(a, b). This algorithm is useful for solving certain types of linear Diophantine equations. The algorithm uses the same basic idea as the Euclidean algorithm, but keeps track of the coefficients x and y at each step.
6. Recursive Algorithm: This approach involves writing a recursive function that calls itself with smaller inputs until the base case is reached. The base case is when one of the inputs is zero, in which case the other input is the GCD.

The main differences between the approaches are their algorithmic complexity, speed, and suitability for different types of problems. The Euclidean algorithm is the most efficient and widely used method for finding the GCD of two numbers, but some of the other approaches may be more suitable for specific types of problems. For example, the Extended Euclidean algorithm is useful for solving linear Diophantine equations, while the Binary GCD Algorithm is faster than the traditional Euclidean algorithm for very large inputs.

Time and Space Complexities for each of the approaches

1. Euclidean Algorithm:
   • Time Complexity: O(log(min(a,b)))
   • Space Complexity: O(1)
2. Prime Factorization:
   • Time Complexity: O(sqrt(n)log(n)), where n is the maximum of a and b
   • Space Complexity: O(sqrt(n)), where n is the maximum of a and b
3. Binary GCD Algorithm:
   • Time Complexity: O(log(min(a,b)))
   • Space Complexity: O(1)
4. Division Algorithm:
   • Time Complexity: O(log(min(a,b))^2)
   • Space Complexity: O(1)
5. Extended Euclidean Algorithm:
   • Time Complexity: O(log(min(a,b)))
   • Space Complexity: O(log(min(a,b)))
6. Recursive Algorithm:
   • Time Complexity: O(log(min(a,b))) (assuming tail recursion)
   • Space Complexity: O(log(min(a,b)))

The Euclidean algorithm and the Binary GCD algorithm are the fastest in terms of time complexity, while the Prime Factorization approach is the slowest. In terms of space complexity, most of the approaches have a constant space complexity, with the exception of the Extended Euclidean Algorithm and the Recursive Algorithm, which have a space complexity proportional to the number of recursive calls. Overall, the Euclidean Algorithm is the most widely used approach due to its fast time complexity and constant space complexity.

Happy Learning – If you require any further information, feel free to contact me.