Finding the Greatest Common Divisor (GCD) of two numbers is a fundamental operation in mathematics and computer science. In this article, we’ll explore three different methods to write a C Program to Find the GCD of Two Numbers. Each method will be explained in detail with code examples and outputs, optimized for clarity and comprehension.

Write a C Program to Find the GCD of Two Numbers

What is GCD?

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 20 and 30 is 10, as it is the largest number that can divide both 20 and 30 without leaving any remainder.

Method 1) C Program to Find the GCD of Two Numbers using the Euclidean Algorithm

The Euclidean algorithm is one of the most efficient ways to find the GCD of two numbers. It is based on the principle that the GCD of two numbers also divides their difference.

Code Example

#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 integers: ");
    scanf("%d %d", &num1, &num2);
    printf("GCD of %d and %d is %d\n", num1, num2, findGCD(num1, num2));
    return 0;
}

Explanation of the Code

1. Initialization: The function findGCD takes two integers a and b as inputs.
2. Looping: The while loop continues until b becomes 0. In each iteration, b is assigned the value of a % b, and a is assigned the previous value of b.
3. Result: When b becomes 0, a holds the GCD of the two numbers.

Output

Enter two integers: 20 30
GCD of 20 and 30 is 10

Method 2) C Program to Find the GCD of Two Numbers using the Recursive Euclidean Algorithm

The Euclidean algorithm can also be implemented recursively, providing a more elegant and concise solution.

Code Example

#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 integers: ");
    scanf("%d %d", &num1, &num2);
    printf("GCD of %d and %d is %d\n", num1, num2, findGCD(num1, num2));
    return 0;
}

Explanation of the Code

1. Base Case: The recursion stops when b becomes 0, at which point a is the GCD.
2. Recursion: The function calls itself with the values b and a % b until the base case is met.

Output

Enter two integers: 48 18
GCD of 48 and 18 is 6

Method 3) C Program to Find the GCD of Two Numbers using the Subtraction Method

The subtraction method is a more intuitive, albeit less efficient, way to find the GCD. It is based on the principle that subtracting the smaller number from the larger one doesn’t change the GCD.

Code Example

#include <stdio.h>

int findGCD(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

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

Explanation of the Code

1. Looping: The while loop continues until the two numbers are equal. In each iteration, the larger number is reduced by the smaller number.
2. Result: Once the two numbers are equal, that number is the GCD.

Output

Enter two integers: 56 98
GCD of 56 and 98 is 14

Finding the GCD of two numbers is a crucial operation with numerous applications in mathematics and computer science. In this article, we covered three different methods to compute the GCD in C:

1. Euclidean Algorithm: Efficient and widely used.
2. Recursive Euclidean Algorithm: A more concise approach.
3. Subtraction Method: An intuitive but less efficient method.

Each method has its advantages, and understanding them will enhance your problem-solving skills in C programming. Whether you prefer the iterative or recursive approach, the key is to grasp the underlying principles that make these algorithms work.