This is a simple program to find the Greatest Common Divisor (GCD) of two given positive numbers.

We wrote and compiled the program on Dev-C++ version 5( beta) compiler installed on a Windows 7 64-bit machine. If you want to try a different C compiler, make sure to modify the existing source code to get an error free program.

Learn following c programming topics before you try the example program.

## Problem Definition

Suppose you want to find GCD of two numbers – **a** and **b**. The C program for GCD has a function called **hcf(a, b)** which is called recursively until remainder is 0. The function uses the following logic on the given input numbers where **a** is greater than or equal to **b**.

`r = a - (a/b * b) `

suppose **a = 24** and **b = 6,** than

r = 24 - (24/6 * 6) r = 24 - 24 = 0 r = 0

Then the value of **b** is the GCD which is **6**.

Note:- number **a** must be greater than or equal to **b**.

## Flowchart – Program for GCD of Two Numbers

## Program Code – Program for GCD of Two Numbers

#include <stdio.h> #include <conio.h> main() { int i,a,b,gcd; int hcf(); /* Read the input numbers */ printf("Enter Two Numbers To Find GCD:"); scanf("%d%d",&a,&b); /* Compute the GCD for given numbers */ gcd=hcf(a,b); /* Print the Result */ for(i=0;i<40;i++) printf("_");printf("\n\n"); printf("GCD of %d and %d is %d\n",a,b,gcd); for(i=0;i<40;i++) printf("_");printf("\n\n"); system("PAUSE"); return 0; } int hcf(p,q) { int r; r=p-(p/q*q); if(r==0) return(q); else return hcf(q,r); }

The important piece of code in the above source code is the call to **hcf(a, b)** function and the function **hcf(a, b)** calling itself recursively.

gcd = hcf(a, b);

The function **hcf (a , b)** evaluate the current value of **a** and **b**, and if the remainder is not equal to **0**, it call itself one more time until the remainder becomes **0**.

int hcf(p,q){int r;r=p-(p/q*q);if(r==0)return(q);elsereturn hcf(q,r);}

## Output

The output of the program is given below. When the user enters 24 and 6, the result is 6 which greatest common divisor (GCD) of 24 and 6.

**Related Articles:**