C Program to Find GCD of Two Numbers

1. Introduction

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two numbers is the largest number that divides both of them without leaving a remainder. The GCD has various applications, especially in number theory and for simplifying fractions. In this guide, we'll demonstrate a C program to find the GCD of two numbers using the Euclidean algorithm.

2. Program Overview

1. Prompt the user to enter two numbers.

2. Implement the Euclidean algorithm to determine the GCD.

3. Display the GCD of the two numbers.

3. Code Program

#include <stdio.h>

// Function to find the GCD of two numbers
int gcd(int a, int b) {
    while(b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;

    // Asking user to input the numbers
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);

    // Printing the GCD
    printf("GCD of %d and %d is: %d", num1, num2, gcd(num1, num2));

    return 0;
}

Output:

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

4. Step By Step Explanation

1. The program starts by defining a function gcd that takes two integers as arguments. This function implements the Euclidean algorithm to compute the GCD.

2. In the Euclidean algorithm, we repeatedly take the remainder when the first number is divided by the second number until the second number becomes 0. At that point, the first number will be the GCD.

3. The main function prompts the user to input two numbers.

4. The GCD of the two entered numbers is then computed by calling the gcd function.

5. Finally, the GCD is displayed.