Program to Find the Greatest Common Divisor (GCD) in C

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 36 and 60 is 12.

We will explore three different methods to find the GCD of two numbers using C programming.

Method 1: Using Euclidean Algorithm

The Euclidean algorithm repeatedly replaces the larger number with its remainder when divided by the smaller number until the remainder becomes zero.

#include <stdio.h>

int findGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    printf("GCD of %d and %d is %d", num1, num2, findGCD(num1, num2));
    return 0;
}
            

Output:

Enter two numbers: 36 60
GCD of 36 and 60 is 12

Method 2: Using Recursion

In this method, we use recursion to apply the Euclidean algorithm.

#include <stdio.h>

int findGCD(int a, int b) {
    if (b == 0)
        return a;
    return findGCD(b, a % b);
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    printf("GCD of %d and %d is %d", num1, num2, findGCD(num1, num2));
    return 0;
}
            

Output:

Enter two numbers: 36 60
GCD of 36 and 60 is 12

Method 3: Using Iteration

In this method, we iterate from the smaller number down to 1 and find the largest number that divides both inputs.

#include <stdio.h>

int findGCD(int a, int b) {
    int gcd = 1;
    for (int i = 1; i <= (a < b ? a : b); i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    printf("GCD of %d and %d is %d", num1, num2, findGCD(num1, num2));
    return 0;
}
            

Output:

Enter two numbers: 36 60
GCD of 36 and 60 is 12