C Program to Find GCD of Two Numbers

Summary: In this programming example, we will learn different ways to find GCD of two numbers in C.

GCD or HCF of two or more numbers is the highest possible positive integer that can divide each of the numbers.

Example: GCD of 15 and 20 is 5.

GCD of two or more numbers is always less than or equal to the minimum of them.

There are different ways to calculate GCD in C.

Method 1: GCD using Loop

#include <stdio.h>
int main() {

    int a, b, gcd = 0; 
    
    printf("Enter two numbers \n");
    scanf("%d",&a);
    scanf("%d",&b);
    
    for(int i=1; i<=a && i<=b; i++){
        if(a%i==0 && b%i==0)
            gcd = i;
    }
    
    printf("GCD: %d", gcd);
}

Output

Enter two numbers 4 16 GCD: 4

In this program the user first inputs the two numbers into a and b.

Then we loop from 1 to the minimum of the two numbers and check if they divide both a and b.

If yes then we store the value of loop variable i.e. i into gcd.

The final value which divides both the input number is the GCD.

Method 2: GCD using the Euclidean Algorithm

In this algorithm, we divide the first number with the second and simultaneously update the first number with the second number and second number with the remainder.

We repeat this process until the remainder comes out to be zero.

The final value of the first number will be the GCD of the two input numbers.

#include <stdio.h>
int main() {

    int a, b, temp; 
    
    printf("Enter two numbers \n");
    scanf("%d",&a);
    scanf("%d",&b);
    
    while(b){
        temp=b;
        b=a%b;
        a=temp;
    }
    
    printf("GCD: %d", a);
}

Output

Enter two numbers 10 20 GCD: 10

Method 3: GCD using Recursion

#include <stdio.h>
int findGCD(int,int);

int main() {

    int a, b, temp; 
    
    printf("Enter two numbers \n");
    scanf("%d",&a);
    scanf("%d",&b);
    
    printf("GCD: %d", findGCD(a, b));
}

//Recursive method to find GCD
int findGCD(int a, int b){
    if(b==0)
        return a;
    findGCD(b,a%b);
}

Output

Enter two numbers 8 14 GCD: 2

This method implements the Euclidean Algorithm using recursion.

In this tutorial, we learned to find GCD of two numbers in C programming language.