C Program to find GCD or HCF Of Two Numbers

Write a C program to find GCD or HCF of Two Numbers

The Highest Common Multiple or the Greatest Common Divisor is the greatest number that exactly divides both numbers. It is possible to calculate this number through simple mathematical calculations. The following algorithm shows how the GCD of two numbers is calculated.

Ex:-

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

Working:-

Step 1. Start

Step 2. Enter two numbers a and b.

Step 3. If a = 0, return b.

Step 4. If b = 0, return a.

Step 5. If a is equal to b return a

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

Step 7. Else return a, b-a

Step 8. Stop

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.

Please Login/Signup to comment