C Program to Find GCD of two Numbers

Introduction

The concept of the Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF), is fundamental in mathematics and is widely used in various applications, including simplifying fractions, cryptographic algorithms, and more. It is the largest number that can evenly divide two numbers without leaving a remainder.

In this article, you will learn how to implement a program in C that calculates the GCD of two numbers using different methods. These methods will showcase how fundamental programming constructs in C can solve mathematical problems effectively.

Finding GCD Using the Euclidean Algorithm

Basic Euclidean Method

The Euclidean algorithm is an efficient method for computing the GCD of two integers. The algorithm is based on the principle that the GCD of two numbers also divides their difference.

1. Initialize two integer variables to store the numbers.

2. Begin a loop that continues until one of the numbers becomes zero.

3. Replace the larger number by the remainder of the division of the two numbers.

4. Print the number that is not zero as the GCD.

   #include <stdio.h>
   
   int gcd(int a, int b) {
       while (b != 0) {
           int temp = b;
           b = a % b;
           a = temp;
       }
       return a;
   }
   
   int main() {
       int num1 = 84, num2 = 18;
       printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
       return 0;
   }

   In this code, the gcd function computes the GCD of num1 and num2 using the Euclidean algorithm. The loop continues to replace the larger number with the remainder until b becomes zero.

Recursive Euclidean Method

The Euclidean method can also be implemented using recursion, which often simplifies the loop logic into a more readable form.

1. Write a recursive function that calculates the GCD.

2. Base case: If the second number is zero, return the first number as the GCD.

3. Recursive case: return the GCD of the second number and the remainder of the first 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 = 120, num2 = 45;
       printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
       return 0;
   }

   The recursive version of the gcd function simplifies the iterative logic into a concise recursive call, making the code easier to understand and maintain.

Conclusion

Calculating the GCD of two numbers in C using the Euclidean algorithm illustrates how compact and efficient C programs can be for solving mathematical problems. Both iterative and recursive approaches offer valuable insights into problem-solving with programming. These techniques not only serve academic purposes but are also applicable in solving real-world problems where computational efficiency is crucial. By mastering these methods, enhance your ability to tackle more complex algorithms effectively.