Write a Program to Find the GCD (HCF) of Two Numbers in C

Write a Program to Find the GCD (HCF) of Two Numbers

Finding the Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two numbers is a fundamental operation in mathematics. The GCD of two numbers is the largest number that divides both of them without leaving a remainder. In this blog post, we will walk you through writing a C program to calculate the GCD of two numbers using the Euclidean algorithm.

1. Understanding the GCD

The GCD of two integers can be calculated using various methods. One of the most efficient and well-known methods is the Euclidean algorithm, which relies on the principle that the GCD of two numbers also divides their difference.

For example, to find the GCD of 48 and 18, we can apply the following steps:

• Calculate 48 mod 18 = 12.
• Now, find GCD(18, 12).
• Calculate 18 mod 12 = 6.
• Now, find GCD(12, 6).
• Calculate 12 mod 6 = 0.
• Since the remainder is now 0, the GCD is 6.

2. Algorithm to Find the GCD

The algorithm to find the GCD using the Euclidean method can be summarized in the following steps:

1. Take two numbers as input.
2. While the second number is not zero, perform the following:
• Calculate the remainder of the first number divided by the second number.
• Replace the first number with the second number and the second number with the remainder.
3. When the second number becomes zero, the first number will be the GCD.

3. Writing the Program

Let’s implement the algorithm in C.

Code Example: Finding the GCD

#include <stdio.h>

int main() {
    int a, b, gcd;

    // Prompt user to enter two numbers
    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    // Store the original values for printing later
    int original_a = a;
    int original_b = b;

    // Calculate GCD using the Euclidean algorithm
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    gcd = a;

    // Output the result
    printf("The GCD of %d and %d is: %d\n", original_a, original_b, gcd);

    return 0;
}

Explanation of the Code

In this program:

• We include the stdio.h header file to use input/output functions.
• We declare three integer variables: a and b to hold the input numbers, and gcd to store the result.
• We prompt the user to enter two integers and read them using scanf.
• We use a while loop to implement the Euclidean algorithm. Inside the loop, we calculate the remainder and update the values of a and b.
• Once the loop exits (when b becomes zero), we assign the value of a to gcd.
• Finally, we print the GCD of the two numbers.

4. Example Output

Here’s an example of how the program works:

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

5. Common Mistakes to Avoid

When implementing this program, here are some common mistakes to be aware of:

• Incorrect loop condition: Ensure that the loop continues until the second number becomes zero.
• Not storing original values: If you need to print the original values of the numbers after calculations, store them in separate variables before modifying them.
• Wrongly using the modulus operator: Ensure the correct use of the modulus operator to find the remainder.

6. Expanding the Program

Now that you have a basic program to find the GCD, consider these ideas for expanding it:

• Allow the user to find the GCD of more than two numbers.
• Implement error handling for negative numbers or non-integer inputs.
• Display the steps taken in the Euclidean algorithm for educational purposes.

7. Conclusion

In this post, we’ve learned how to write a C program to find the GCD (HCF) of two numbers using the Euclidean algorithm. We explained the logic behind the implementation, provided a complete code example, and discussed common pitfalls to avoid.

Mastering the concept of GCD is useful in various mathematical applications and algorithms. By practicing programs like this, you enhance your programming skills and deepen your understanding of algorithms. Happy coding!