C Program to find GCD or HCF Of Two Numbers

GCD or HCF of Two numbers in C

Here, in this section we will discuss GCD or HCF of two numbers in C. The Highest Common Multiple or the Greatest Common Divisor is the greatest number that exactly divides both numbers.

There are many methods to calculate GCD:

  • Using Prime Factorisation,
  • Euclid’s Algorithm,
  • Lehmer’s GCD algorithm, etc

It is possible to calculate this number through simple mathematical calculations. The following algorithm shows how the GCD of two numbers is calculated.

Example:-

The H.C.F or G.C.D of 12 and 14 is 2.

The H.C.F or G.C.D of 16 and 12 is 4

GCD

Working:-

Step 1. Start

Step 2. Take two integers numbers from the user and store them in variable say a and b.

Step 3. Create a function say gcd() that take two parameters as arguments.

Step 4. Inside function, if a = 0, return b.

Step 5. If b = 0, return a.

Step 6. If a is equal to b return a

Step 7. If a is greater than b, return a – b, and b

Step 8. Else return a, b-a

Step 9. Call function gcd() recursively.

Step 8. Stop

GCD or HCF of two numbers in C
Competitive Coding Techniques

C program to calculate GCD of two numbers

 

// C program to calculate GCD of two numbers 
#include<stdio.h>
// The code used a recursive function to return gcd of p and q 
 int gcd(int p, int q) 
 { 

   // checking divisibility by 0 
    if (p == 0) 
       return q; 
if (q == 0) return p; // base case if (p == q) return p;
// p is greater
if (p > q) return gcd(p-q, q); else return gcd(p, q-p); } // Driver program to test above function int main() {
int p = 98, q = 56; printf("GCD of %d and %d is %d ", p, q, gcd(p, q)); return 0; }

Output

The GCD of 98 and 56 is 14.