1) Divide the larger number by the smaller.
2) If the division can be done exactly then the HCF is the smaller number. If there is a remainder then the HCF is the same as the HCF of the remainder and the smaller number - so repeat step 1 with these two numbers.
For instance, to find HCF(17, 20):
20/17 = 1, with remainder 3
so the HCF is the same as HCF(17, 3):
17/3 = 6 with remainder 1
so the HCF is the same as HCF(3, 1):
3/1 = 3; this is exact, so the HCF is 1.
Programme
#include
#include
void hcf(int a,int b);
main()
{
int a,b,t;
clrscr();
printf("Enter two nos : ");
scanf("%d%d",&a,&b);
if(b>a)
{
t=a;
a=b;
b=t;
}
hcf(a,b);
}
void hcf(int a,int b)
{
int x;
x=a%b;
if(x==0)
{
printf("\n\t hcf = %d",b);
getch();
}
else
hcf(b,x);
}
