What is GCD?

GCD is defined as the greatest common divisor of two numbers. Have you heard of H.C.F. in elementary mathematics? GCD is exactly same as HCF. For example, G.C.D of 4 and 8 will be 4 as 4 is the largest number which divides both 4 and 8.

Similarly, G.C.D. of 12 and 18 will be 6 as 6 is the largest number which divides both 12 and 18.

Start with two integers as input.
Find the smaller of the two integers.
Initialize a variable to store the greatest divisor found so far.
Run a loop from 1 to the smaller integer.
For each number in the loop, check if it divides both integers.
If yes, update the greatest divisor variable with this number.
After the loop ends, the stored greatest divisor will be the GCD.
Return or print the GCD.

#include <stdio.h>
#include <math.h>
struct Solution {
    // Function pointer for GCD
    int (*gcd)(int, int);
};

// Function to find the minimum of two numbers
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}

// Implementation of GCD function (Brute Force Approach)
int gcdImpl(int n1, int n2) {
    // Initialize gcd as 1
    int gcdd = 1;

    // Run a loop from 1 to minimum of the two numbers
    for (int i = 1; i <= min(n1, n2); i++) {
        // If i divides both numbers, update gcd
        if (n1 % i == 0 && n2 % i == 0)
            gcdd = i;
    }

    // Return the greatest common divisor
    return gcdd;
}

// Driver code (main function)
int main() {
    // Create an object of Solution
    struct Solution obj;

    // Bind the gcdImpl function to the struct
    obj.gcd = gcdImpl;

    // Example inputs
    int n1 = 5, n2 = 10;

    // Call gcd function through the struct object
    printf("The GCD of the two integers %d and %d is %d", n1, n2, obj.gcd(n1, n2));

    return 0;
}

Complexity Analysis

Time Complexity: O(min(n1,n2))

Space Complexity: O(1)

Euclidean Algorithm

Algorithm