C Program to Find GCD of two Numbers

Here you will learn different ways to calculate the GCD of two numbers in C with the help of a programming example.

The primary prerequisite to understanding the below example code:

Before explaining what is the GCD ( greatest common divisor) is let’s see the problem statement.

Problem Statement:

Given two numbers, Find the gcd of two given numbers with the help of the C program.

Now let’s understand the term GCD and see the approach to solve the above-mentioned problem.

Greatest Common Divisor – GCD:

The greatest common divisor (GCD) is a large positive common divisor for given two or more integers. It is also termed the highest common factor (HCF) or the greatest common factor (GCF).

So for two integers X, and Y, the greatest common divisor of X and Y is denoted gcd(X, Y). For example, the greatest common factor of 6 and 15 is 3, since both the numbers can be divided by 3.

Note: Also, you should remember that the GCD of any two numbers is never negative or 0.

Now you are thinking that how I can calculate the GCD of two given numbers. Don’t worry I will explain it but for now, you can understand that there are two common ways to determine the greatest common divisor of two numbers:

By finding the common divisors.
By Euclid’s algorithm.

1. By finding the common divisors:

For two positive integers X, Y you can use the below-given steps to find the GCD:

Step 1: Find the divisors of “X”.
Step 2: Find the divisors of “Y”.
Step 3: Enlist the common divisors of “X” and “Y”.
Step 4: Now find the Greatest divisor which is the greatest of both “X” and “Y”.

For example,

Factors of 6 are: 1, 2, 3, 6

Factors of 15 are: 1, 3, 5, 15

Common Factors of 6 and 15 are the numbers that are in both lists: 1, 3

In this list, the greatest factor is 3. Hence, the GCD of 6 and 15 is 3.

#include <stdio.h>
#include <math.h>


int min(int num1, int num2)
{
    return ((num1 <num2)?num1:num2);
}

int gcdOfTwoNum(int num1,int num2)
{
    int i, gcdValue = 1;
    const int maxLoop = min(num1, num2);
    for(i=1; i<= maxLoop; i++)
    {
        if(((num1%i)==0)&&((num2%i)==0))
        {
            gcdValue=i;
        }
    }
    return gcdValue;
}

int main()
{
    int a, b;
    printf("Enter number 1: ");
    scanf("%d",&a);

    printf("\nEnter number 2: ");
    scanf("%d",&b);

    const int gcdValue = gcdOfTwoNum(a, b);
    printf("\nThe GCD of the two numbers %d and %d is %d\n",a,b,gcdValue);

    return 0;
}

Output:

You can also optimize the above code to run the loop in reverse order starting from maxLoop to 1. You just need to break the loop as soon as you find a divisor. See the code.

#include <stdio.h>
#include <math.h>


int min(int num1, int num2)
{
    return ((num1 <num2)?num1:num2);
}

int gcdOfTwoNum(int num1,int num2)
{
    int i, gcdValue = 1;
    const int maxLoop = min(num1, num2);
    for(i = maxLoop; i>= 1; i++)
    {
        if(((num1%i)==0)&&((num2%i)==0))
        {
            gcdValue=i;
            break; //breaking the loop
        }
    }
    return gcdValue;
}

int main()
{
    int a, b;
    printf("Enter number 1: ");
    scanf("%d",&a);

    printf("\nEnter number 2: ");
    scanf("%d",&b);

    const int gcdValue = gcdOfTwoNum(a, b);
    printf("\nThe GCD of the two numbers %d and %d is %d\n",a,b,gcdValue);

    return 0;
}

2. Euclid’s Algorithm for Greatest Common Divisor:

The following are the steps to find the GCD of two positive integers X and Y using Euclid’s algorithm.

1:- If X = 0, then GCD (X, Y) = Y as GCD (0, Y) = Y.

2:- If Y = 0, then GCD (X, Y) = X as GCD (X, 0) = X.

3:- If both X≠0 and Y≠0 and X >Y, you can write ‘X’ in the quotient remainder form (X = Y× q + rem) where q is the quotient and rem is the remainder.

4:- If X = Y x q + rem and Y≠0 then GCD(X, Y) = GCD(Y, rem), so find the GCD (Y, rem).

5:-You need to repeat this process until we get the remainder as 0.

Example:

Find the GCD of 16 and 14

X= 16, Y=14
X ≠0
Y ≠0
Use long division to find that 16/14 = 1 with a remainder of 2. We can write this as: 16 = (14 * 1 + 2)
Find GCD(16,14), since GCD(16, 14)=GCD(14,2)

X=16, Y=2

X ≠0
Y ≠0
Use long division to find that 16/2 = 8 with a remainder of 0. We can write this as:
16 = (8*2 + 0)
Find GCD(2,0), since GCD(16, 2)=GCD(2,0)

X=2, Y=0

X ≠0
Y =0, GCD(2,0)=2

C code to perform GCD using recursion:

The following C code to find the GCD using the recursion and Euclid’s algorithm.

#include <stdio.h>
#include <math.h>


int gcdOfTwoNum(int num1,int num2)
{
    if (num1 == 0)
    {
        return num2;
    }
    if (num2 == 0)
    {
        return num1;
    }
    // base case
    if (num1 == num2)
    {
        return num1;
    }
    // num1 is greater
    if (num1 > num2)
    {
        return gcdOfTwoNum(num1-num2, num2);
    }
    return gcdOfTwoNum(num1, num2-num1);
}

int main()
{
    int a, b;
    printf("Enter number 1: ");
    scanf("%d",&a);

    printf("\nEnter number 2: ");
    scanf("%d",&b);

    const int gcdValue = gcdOfTwoNum(a, b);
    printf("\nThe GCD of the two numbers %d and %d is %d\n",a,b,gcdValue);

    return 0;
}