HCF (Highest Common Factor) and GCD (Greatest Common Divisor) of two numbers
The recursive method of finding the HCF of two numbers was given by renowned mathematician Euclid. The formula is given below:
GCD (n, m) = GCD (n, m) if n<m)
= m if n>=m and n mod m=0
= GCD (m, n mod m) otherwise
Write a program to input any two numbers and find the GCD of two numbers by using the recursive function.
#include<stdio.h>
#include<conio.h>
int GCD(int n,int m)
{
if((n>=m) && (n%m)==0))
return(m);
else
return(GCD(m,n%m));
}
void main()
{
int n,m,result;
clrscr();
printf("\nEnter any first number:");
scanf("%d",&n);
printf("\nEnter any second number:");
scanf("%d",&m);
result=GCD(n,m);
printf("\nGCD of two numbers %d and %d is:%d",n,m,result);
getch();
}
Output: Enter any first number: 12
Enter any second number: 6
GCD of two numbers 12 and 6 is: 6