C Program to Find GCD of Two Numbers

GCD stands for Greatest Common Divisor. GCD of two numbers in C is the largest positive integer that completely divides both the given numbers.

Example: GCD(10,15) = 15, GCD(12,15) = 3.

Write a C Program to Find the GCD of two numbers.

1. Take two numbers as input.
2. Find the greater of the two numbers.
3. Keep on dividing the greater number by the smaller number until remainder becomes 0.
4. When the remainder becomes 0 print the smaller number i.e., the denominator as the output.
5. Exit.

There are several ways to find the GCD of two numbers in C language. Let’s look at the five different approaches to write a C program to calculate the GCD of two numbers.

• GCD of Two Numbers in C using While Loop
• GCD of Two Numbers in C using For Loop
• GCD of Two Numbers in C using Recursion
• GCD of Two Numbers in C using Euclidean Algorithm
• GCD of Two Numbers in C using Recursive Euclidean Algorithm

In this approach, we find the GCD of two numbers using a while loop.

Here is the source code of the C program to find the GCD of two numbers using a while-loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to find the GCD of two integers using While-loop
 */
#include<stdio.h>
 
void main()
{
    int num1, num2, gcd, remainder, numerator, denominator;
 
    printf("Enter two numbers\n");
    scanf("%d %d", &num1, &num2);
    if (num1 > num2)
    {
        numerator = num1;
        denominator = num2;
    }
    else
    {
        numerator = num2;
        denominator = num1;
    }
    remainder = numerator % denominator;
    while (remainder != 0)
    {
        numerator   = denominator;
        denominator = remainder;
        remainder   = numerator % denominator;
    }
    gcd = denominator;
    printf("GCD of %d and %d = %d\n", num1, num2, gcd);
}

1. Take the two numbers num1 and num2 as input.
2. Store the greater number in the variable numerator and the smaller number in the variable denominator.
3. Run the while loop until the remainder becomes ‘0’. Inside the while loop keep on dividing the numerator by denominator and store the value in the remainder variable.
4. When the value of the remainder variable becomes ‘0’ come out of the loop and store the value of the denominator in the gcd variable.
5. Print the gcd.

Example:
Consider, the two numbers 12 and 15, first find the greater of the two numbers and store the greater in the numerator and smaller in the denominator i.e., numerator=15 and denominator=12. Divide the numerator by the denominator and store the value in the remainder variable i.e., remainder = 15%12 = 3. Now, enter the while loop and check if the remainder value is ‘0’ or not. Now, assign the value of the denominator to the numerator and the value of the remainder to the numerator i.e., numerator=12 and denominator=3 then calculate the remainder of the two variables i.e., remainder = 12%3 = 0. Now, check the while loop condition again, this time remainder = 0, therefore come out of the loop and store the value of the denominator in gcd i.e., gcd = 3. Now, print gcd as 3.

Time Complexity: O(log(min(a,b)))
The above program for finding GCD of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the numerator is divided by the denominator.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 12 and 15.

Enter the two numbers: 12 15
GCD of 12 and 15 = 3

Testcase 2: The numbers entered by the user to calculate gcd are 50 and 30.

Enter the two numbers: 50 30
GCD of 50 and 30 = 10

In this approach, we find the GCD of two numbers using for-loop.

Here is the source code of the C program to find the GCD of two numbers using for loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to find the GCD of two integers using for-loop
 */
#include<stdio.h>
void main()
{
    int n1, n2, i, gcd;
 
    printf("Enter two integers: ");
    scanf("%d %d", &n1, &n2);
 
    int min = (n1 < n2)? n1:n2;  // to find minimum of the two numbers.
 
    for(i=min; i >=1; --i)
    {
        // Checks if i divides both the integers
        if(n1%i==0 && n2%i==0)
        {
            gcd = i;
            break;
        }
    }
    printf("G.C.D of %d and %d is %d", n1, n2, gcd);
}

1. Take the two integers n1 and n2 as input.
2. Store the minimum of the two integers in the variable min.
3. Run the for loop from i=min to i>=1 and decrease the value of i by 1 after each iteration.
4. Divide both the numbers n1 and n2 by i, if both gives remainder = 0 then store the value of i in gcd variable and break the for loop. (We are breaking the for loop because we are checking for GCD from the greatest number possible for GCD. So, the 1st greatest number that divides both the number completely is the GCD of the two numbers.)
5. Print the gcd.

Example:
Consider the two numbers are n1=10 and n2=15. Find minimum of the two numbers and store it in the variable min i.e., min=10. Run the for loop from i = min to 1 and check if i divides both n1 and n2 completely. At the beginning i = 1, 10%10 gives the remainder as 0 but 15 %10 is 5 so, the if condition is false, decrement the value of i to 9 and again check the if condition. Repeat this step until if condition becomes true. Check for i=5, so 10%5=0 and 15%5=0 so, enter the if condition. Inside if statement assign the value of i to variable gcd. Now, break the condition i.e., come out of the for loop and print the value of gcd. Therefore, gcd of 10 and 15 is 5.

Time Complexity: O(min(n1,n2)))
The above program for finding GCD of two numbers has a time complexity of O(min(n1,n2)), as the for loop runs for minimum of number of times of n1 and n2.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: The numbers entered by the user to calculate gcd in this case are 10 and 15.

Enter the two numbers: 10 15
G.C.D of 10 and 15 is 5

Testcase 2: The numbers entered by the user to calculate gcd are 15 and 24.

Enter the two numbers: 15 24
G.C.D of 15 and 24 is 3

In this approach, gcd() function is used to find the GCD of two entered numbers using recursion.

Here is the source code of the C program to find the GCD of two numbers using recursion. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to find GCD of given Numbers using Recursion
 */
#include<stdio.h>
 
int gcd(int, int);
 
int main()
{
    int a, b, result;
 
    printf("Enter the two numbers to find their GCD: ");
    scanf("%d%d", &a, &b);
    result = gcd(a, b);
    printf("The GCD of %d and %d is %d.\n", a, b, result);
}
 
int gcd(int a, int b)
{
    while (a != b)
    {
        if (a > b)
        {
            return gcd(a - b, b);
        }
        else
        {
            return gcd(a, b - a);
        }
    }
    return a;
}

In this C Program, we are reading the two integer numbers using ‘a’ and ‘b’ variable. The gcd() function is used to find the GCD of two entered integers using recursion.

While loop is used to check that both the ‘a’ and ‘b’ variable values are not equal. If the condition is true then execute the loop. Otherwise, return the value of ‘a’ variable. If else condition statement is used to check the value of ‘a’ variable is greater than the value of ‘b’ variable.

If the condition is true, then recursively call the gcd() function passing the values (a-b, b). Otherwise, if the condition is false, then recursively call the gcd() function passing the values (a, b-a). Run this until while loop condition becomes false and then return the value of ‘a’ as output.

Example:
Consider, the two numbers a and b are 15 and 20. Enter the gcd() function and check if both are equal or not. Since, 15! = 20 enter the while-loop. Inside the while-loop we see that a<b, therefore, enter the else statement and recursively call gcd function passing the values (a, b-a) i.e., (15,5).

Again, follow the same procedure as above. This time a>b, therefore, execute the if statement and call the function gcd() passing the values (a-b, b) i.e., (10,5).

Repeat the same process again. This time a>b, therefore, execute the if statement and call the function gcd() passing the values (a-b, b) i.e., (5,5).

Now, a=b, therefore do not enter the while loop and return the value of ‘a‘ i.e., 5 as gcd.

Time Complexity: O(log(min(a,b)))
The above program for finding GCD of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the lesser number is subtracted from the greater number until both becomes equal.

Space Complexity: O(log(min(a,b)))
In the above program, space complexity is O(log(min(a, b))) as the value of a and b gets stored in the memory until the recursive function gets terminated.

Testcase 1: In this case, the numbers entered by the user to find gcd using recursion are 15 and 20.

Enter the two numbers to find their GCD: 15 20
The GCD of 15 and 20 is 5.

Testcase 2: The numbers entered by the user to find gcd using recursion are 50 and 20.

Enter the two numbers to find their GCD: 50 20
The GCD of 50 and 20 is 10.

In this approach, we find the GCD of two numbers using Euclidean Algorithm.

Here is the source code of the C program to find the GCD of two numbers using Euclidean Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to find GCD of two Numbers using Euclidean Algorithm
 */
#include<stdio.h>
 
int gcd(int x, int y)
{
    int r = 0, a, b;
    a = (x > y) ? x : y; // a is greater number
    b = (x < y) ? x : y; // b is smaller number
 
    r = b;
    while (a % b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}
 
int main(int argc, char **argv)
{
    printf("Enter the two numbers: ");
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    printf("The GCD of two numbers is: %d", gcd(x, y));
    return 0;
}

In this C Program, we are reading the two integer numbers using ‘x’ and ‘y’. The gcd() function is used to find the GCD of two entered integers without recursion.

This program is same as the “using while” program, the only difference is that we are implementing it using function.

The while loop terminates when a modulus b becomes 0, and r is returned back to the main function.

Example:
Consider, the two numbers 12 and 15, first find the greater of the two numbers and store the greater in the variable a and smaller in the variable b i.e., a=15 and b=12.

In the while loop check if a%b is not equal to 0. Since, 15%12 = 3 which is not equal to 0, enter the while loop. Store the value of a%b in the variable r i.e., r=3. Assign the value of b in a and r in b i.e., a=12 and b=3.

Now, again check the while loop, since 12%3=0 come out of the loop and return the value of r i.e., 3. In the main function print the value returned by r as GCD. Therefore, gcd of 15 and 12 is 3.

Time Complexity: O(log(min(a,b)))
The above program for finding GCD of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the a is divided by b.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: In this case, the numbers entered by the user to calculate gcd using the Euclidean algorithm are 12 and 15.

Enter the two numbers: 12 15
The GCD of two numbers is: 3

Testcase 2: The numbers entered by the user to calculate gcd using the Euclidean algorithm are 50 and 20.

Enter the two numbers: 50 20
The GCD of two numbers: 10

In this approach, we find the GCD of two numbers using Recursive Euclidean Algorithm.

Here is the source code of the C program to find the GCD of two numbers using Recursive Euclidean Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to find GCD of two Numbers using Recursive Euclidean Algorithm
 */
#include<stdio.h>
 
int gcd_algorithm(int a, int b)
{
    int x = (a > b) ? a : b; // a is greater number
    int y = (a < b) ? a : b; // b is smaller number
 
    if (y == 0) 
    {
        return x;
    } 
    else 
    {
        return gcd_algorithm(y, (x % y));
    }
}
 
int main()
{
    int num1, num2, gcd;
    printf("\nEnter two numbers to find gcd using Euclidean algorithm: ");
    scanf("%d%d", &num1, &num2);
    gcd = gcd_algorithm(num1, num2);
 
    printf("The GCD of %d and %d is %d\n", num1, num2, gcd);
    return 0;
}

In this C Program, we are reading the two integer numbers using ‘num1’ and ‘num2’. The gcd_algorithm() function is used to find the GCD of two entered integers using recursive Euclidean Algorithm.

Store the greater of the two numbers in variable x and smaller number in variable y. If y becomes 0 then return x else recursively call the gcd_algorithm() function with parameters (y,(x%y)). Repeat this process until y becomes 0.

Example:
Consider the two numbers are 20 and 12. The greater number i.e., 20 is stored in x and the smaller number i.e., 12 is stored in y. Check the condition if y==0, since condition is false execute the else statement and recursively call the gcd_algorithm() function by passing the values as (y,(x%y)) i.e., (12,8). Now, repeat the same process. X=12 and y=8. As y is not equal to 0 again execute the else part and call the recursive function gcd_algorithm() by passing the values as (y,(x%y)) i.e., (8,4). In the next step again the same process will be followed and the values that will be returned to the function are (4,0).
Now, x=4 and y=0. Check the if condition, this time the condition i.e., y==0 becomes true and hence x i.e., 4 is returned as GCD. In the main function print 4 as GCD.

Time Complexity: O(log(min(x,y)))
The above program for finding GCD of two numbers has a time complexity of O(log(min(x,y))), as the gcd_algorithm() function runs for minimum of number of times x is divided by y.

Space Complexity: O(log(min(x,y)))
In the above program, space complexity is O(log(min(x, y))) as the value of x and y gets stored in the memory until the recursive function gets terminated.

Testcase 1: In this case, the numbers entered by the user to calculate gcd using the Euclidean algorithm are 12 and 20.

Enter two numbers to find gcd using Euclidean algorithm: 12 20
The GCD of 12 and 20 is 4

Testcase 2: The numbers entered by the user to calculate gcd using Euclidean algorithm are 18 and 144.

Enter two numbers to find gcd using Euclidean algorithm: 18 144
The GCD of 18 and 144 is 18

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.