C Program to Find GCD of Two Numbers

This C program finds the Greatest Common Divisor (GCD) of two given numbers.

Problem Statement

Write a C program that reads two integers from the user and calculates their greatest common divisor (GCD) using the Euclidean algorithm. The program should then display the calculated GCD.

Your program should adhere to the following specifications:

1. Prompt the user to enter two integers.
2. Read the input values from the user.
3. Implement a function named gcd that takes two integers as parameters and returns their GCD using the Euclidean algorithm.
4. The gcd function should be implemented recursively.
5. Display the calculated GCD on the screen.

Note:

• The program should handle positive integers.
• If either of the input numbers is zero, the GCD is considered to be the non-zero number.
• The program should handle cases where the user enters negative integers, but the GCD will always be positive.

C Program to Find GCD of Two Numbers

#include <stdio.h>

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

int main() {
    int num1, num2;

    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);

    printf("The GCD of %d and %d is %d\n", num1, num2, result);

    return 0;
}

How it Works

1. The program starts by including the necessary header file stdio.h for input/output operations.
2. Next, a function named gcd is defined. This function takes two integers, a and b, as parameters and returns their GCD.
3. Inside the gcd function, there is a base case check. If b is equal to 0, it means that a is the GCD, so it is returned.
4. If the base case is not satisfied, the function calls itself recursively with the arguments b and a % b. This step applies the Euclidean algorithm by finding the remainder of a divided by b.
5. The main function is implemented next. It begins by declaring two integer variables num1 and num2 to store the user’s input.
6. The user is prompted to enter two numbers using the printf function and the scanf function is used to read the input values into num1 and num2.
7. The gcd function is called with num1 and num2 as arguments, and the result is stored in the result variable.
8. Finally, the calculated GCD is displayed on the screen using the printf function.

When the program is executed, it follows this sequence of steps, prompting the user for input, calculating the GCD using the gcd function, and displaying the result on the screen.

Input /Output

In this example, the user enters the numbers 24 and 36. The program then calculates the GCD using the Euclidean algorithm and prints the result, which is 12.