How to Get the GCD Of Two Numbers in C

The greatest common divisor (GCD) is the largest positive integer that is also a common divisor of a given set of positive integers. It is also known as the highest common factor (HCF) or the greatest common factor (GCF).

The greatest common divisor of a pair of positive integers (a, b) is defined as the greatest positive number that is both positive integers' common factor (a, b). The GCD of any two numbers is never negative or zero since the smallest positive integer shared by any two numbers is always 1.

For example: let's take two numbers 75 and 30 so the highest number that can divide both numbers will be 15.

Explanation: The numbers that can divide both 75 and 30 are [1,3,5,15] so the highest number among these is 15 so it will be the GCD of 75 and 30.

Example 2: let's take two numbers 128 and 32 so the highest number that can divide both numbers will be 32.

Explanation: The numbers that can divide both 128 and 32 are [1,2,4,8,16,32] so the highest number among these is 32 so it will be the GCD of 128 and 32.

Calculate the GCD of Two Numbers in C

We may deduce from the examples above that the largest number that can divide both numbers is less than the smallest number that can divide both input numbers. As a result, we may create a naive method in which we test each number beginning with the lowest number between both the two integers and making our way up to 1. As a result, the GCD of the two numbers will be whatever number comes first and entirely divides both input numbers.

Example:

Input Numbers: N1 = 132 & N2 = 24

Smallest Number: N2 = 24

We will start a loop from 24 that will end at 1. We will then find the first number that will completely divide both numbers N1 and N2, in this case, it is 12. So the GCD of N1 and N2 will be 12.

Algorithm of the above approach to find GCD:

Declare two variables num1 and num2.
Initialize both variables.
Find the minimum number between both the number and store it in a different variable(minNum).
Start a loop from minNum to 1.
Now check if the num1 and num2 are divisible by the current iterating number and then store the result of it in another variable and come out of the loop. If they are not divisible then continue the same step.
Print the result.

C Program of the above algorithm

#include <stdio.h>
int main()
{
    int num1, num2, i;
    //Accepting and storing input of two numbers from user
    printf("Enter two numbers: ");
    scanf("%d ", &num1);
    scanf("%d ",  &num2);
   
    int minNum=0;
    int result = 1;
   
    //Calculating smallest number among num1 and num2
    if(num1<num2){
        minNum = num1;
    } else {
        minNum = num2;  
    }
    //loop from minNum to 1
    for( i = minNum; i > 1; --i )
    {
        //check if both num1 and num2 is divisible by i or not
        //store the outcome and break out of the loop
        if(num1%i == 0 && num2%i == 0){
            result = i;
            break;
        }        
    }
    //Print the result
    printf("GCD of %d and %d is %d", num1, num2, result);
    return 0;
}

You can run this code on Interviewbit.

Input: 132, 24

Output: GCD of 132 and 24 is 12.

Explanation: The smallest number among 132 and 24 is 24 so the loop starts from 24 and checks if 132 and 24 are divisible by 24 or not since both are not divisible so the loop will continue to run and now it will check for 23 and so on until the loop reaches to 12 where both numbers will be divisible by 12 so it will store the result and break out of the loop and then print the result.

Time Complexity: Since the loop is running for the smallest number(n) to 1 so the time complexity will be O(n).

Space Complexity: It's not taking any extra space other than some variables which are unrelated to the input so the space complexity of this algorithm will be O(1).

We can reduce the time complexity of this algorithm by using an efficient approach.

Efficient Approach: Euclidean Algorithm

The following facts serve as the foundation for the algorithm:

GCD does not change when we subtract a smaller number from a bigger number (we reduce a larger number). So, if we continue to subtract the larger two values, we obtain GCD.
Instead of subtracting, divide the smaller integer, and the procedure will terminate when we discover the remainder 0.

We may begin by determining the lowest integer between 2 and using that number as the divisor. The greatest component will be our dividend. Then we divide it till the remainder reaches zero. If the remainder exceeds zero.

The remainder will then become a divisor, and the current divisor will become a dividend. And must be repeated till the remainder equals zero.

Example: Given two numbers: N1=132, N2=24.
See the following image for a better understanding

In the figure above, we divide the integer till we receive a residual of 0. When the remainder equals zero, the current divisor is the GCD.

Algorithm of this Approach:

Define a function that takes two arguments divisor and dividend.

Now in the function check if the divisor divides the dividend entirely or not. Return the divisor if it divides it entirely otherwise.

Recursively invoke the function by supplying the divisor as the remainder of the divisor and dividend. In addition to the dividend as the current divisor.

C program for the above algorithm

#include <stdio.h>
 
//Function to calculate GCD
int gcd(int divisor, int dividend)
{
    //Calculating remainder
    int remainder = dividend % divisor;
    //Base condition
    //If remainder is 0 then divisor will be GCD
    if(remainder == 0)
    {
        return divisor;
    }
    //Recursive call to find GCD
    return gcd(remainder, divisor);
}
 
int main()
{
    int num1, num2;
    //Accepting and storing input of two numbers from user
    printf("Enter two numbers: ");
    scanf("%d ", &num1);
    scanf("%d ",  &num2);
   
    int dividend, divisor;
    //dividend will be the number which is gretest among the input
    if(num1 > num2){
        dividend = num1;
    } else {
        dividend = num2;
    }
    //Divisor will be the number which is lowest among the input
    if(num1 < num2){
        divisor = num1;
    } else {
        divisor = num2;
    }
    //Calling function to calculate GCD
    int ans = gcd(divisor, dividend);
    //Print the result
    printf("GCD of %d and %d is %d", num1, num2, ans);
    return 0;
}

You can run this code on Interviewbit.

Input: 132, 24

Output: GCD of 132 and 24 is 12.

Time Complexity: O(log(min(num1,num2)) which is equivalent to O(log(n)).

Space Complexity: O(1), no extra space is used other than some variables.

Conclusion:

GCD (Greatest Common Divisor) is a mathematical tool that specifies the number that may divide both integers. We've seen the Java code that was utilized to implement the algorithm. We also comprehended the algorithm's analysis in order to assess how optimal the algorithm is. The best method for calculating the GCD of two integers (Euclid's Algorithm) significantly reduces complexity during competitive programming.