GCD of Two Numbers | Program to Find GCD or HCF Efficiently

GCD of Two Numbers | Program to Find GCD or HCF Efficiently

GCD of Two Numbers | Program to Find GCD or HCF Efficiently

The GCD (Greatest Common Divisor), also known as the HCF (Highest Common Factor), of two integers is the largest integer that divides both numbers without leaving a remainder. This concept is widely used in mathematics, cryptography, and computational tasks.

What Is the GCD of Two Numbers?

  • For example, the GCD of 1818 and 2424 is 66, as 66 is the largest number that divides both 1818 and 2424 without a remainder.

Methods to Calculate GCD

Here are three common methods to find the GCD of two numbers:

1. Iterative Approach

This method uses a simple loop to find the largest divisor of both numbers.

Algorithm:

  1. Identify the smaller number between the two inputs.
  2. Iterate from the smaller number down to 11.
  3. Find the first number that divides both inputs without a remainder.

Code Implementation (C):

c

#include <stdio.h>

int findGCD(int a, int b) {
int small = a > b ? b : a;
for (int i = small; i >= 1; i–) {
if (a % i == 0 && b % i == 0) {
return i;
}
}
return 1; // Default case if no other divisor is found
}

int main() {
int num1 = 18, num2 = 24;
printf(“GCD of %d and %d is: %d\n”, num1, num2, findGCD(num1, num2));
return 0;
}

2. Using Recursion

The recursive method applies Euclid’s Algorithm, which is based on the property:

GCD(a,b)=GCD(b,a%b)\text{GCD}(a, b) = \text{GCD}(b, a \% b)

The recursion terminates when b=0b = 0, at which point aa is the GCD.

Code Implementation (C):

c

#include <stdio.h>

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

int main() {
int num1 = 18, num2 = 24;
printf(“GCD of %d and %d is: %d\n”, num1, num2, gcd(num1, num2));
return 0;
}

3. Using Command-Line Arguments

This approach is particularly useful for running the program directly from a terminal, where the inputs are provided as arguments.

Code Implementation (C):

c
#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[]) {
if (argc != 3) {
printf(“Usage: %s <num1> <num2>\n”, argv[0]);
return 1;
}int a = atoi(argv[1]);
int b = atoi(argv[2]);
int small = a > b ? b : a;

for (int i = small; i >= 1; i–) {
if (a % i == 0 && b % i == 0) {
printf(“GCD of %d and %d is: %d\n”, a, b, i);
return 0;
}
}
return 1;
}

Time Complexity of GCD Methods

  1. Iterative Approach: O(min⁡(a,b))O(\min(a, b))
  2. Euclid’s Algorithm (Recursive): O(log⁡(min⁡(a,b)))O(\log(\min(a, b)))

Example Outputs

Input:

  • Numbers: 1818 and 2424

Output:

  • GCD: 66

Applications of GCD

  1. Cryptography: Used in algorithms like RSA.
  2. Fractions: Simplifying fractions to their lowest terms.
  3. LCM Calculation: GCD helps compute the LCM using the formula: LCM(a,b)=∣a⋅b∣GCD(a,b)\text{LCM}(a, b) = \frac{|a \cdot b|}{\text{GCD}(a, b)}