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.
Contents
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.
\begin{aligned} &r = a - (a/b * b) \end{aligned}
Suppose and
than
\begin{aligned} &r = 24 - (24/6 * 6)\\ &r = 24 - 24 = 0\\ &r = 0 \end{aligned}
Then the value of is the GCD which is
. Note:- number
must be greater than or equal to
.
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 function and the function
calling itself recursively.
gcd = hcf(a, b);
The function evaluate the current value of
and
, and if the remainder is not equal to
, it call itself one more time until the remainder becomes
.
int hcf(p,q) { int r; r=p-(p/q*q); if(r==0) return(q); else return hcf(q,r); }
Output
The output of the program is given below. When the user enters and
, the result is
which greatest common divisor (GCD) of
and
.
Enter Two Numbers To Find GCD:24 6 ------------------------------------------ GCD of 24 and 6 is 6 ------------------------------------------