**Definition of HCF (Highest common factor):**

HFC is called Greatest Common Divisor (GCD).
HCF of Two Numbers is a Largest Positive Numbers which can divide both numbers
without any remainder.

For example : HCF of 4 and 8 is 2 since 2 is the largest positive number which can dived 4 as well as 8 without a remainder.

For example : HCF of 4 and 8 is 2 since 2 is the largest positive number which can dived 4 as well as 8 without a remainder.

**Logic of HCF or GCD of any two numbers:**

In HCF we try to find any largest number which can divide both the number.

For example: HCF or GCD of
20 and 30

Both number 20 and 30 are
divisible by 1, 2,5,10.

HCF=max (1, 2, 3, 4, 10) =10

Logic for writing program:

It is clear that any number is not divisible by greater than number itself. In case of more than one numbers, a possible maximum number which can divide all of the numbers must be minimum of all of that numbers.

For example: 10, 20, and 30

Min (10, 20,
30) =10 can
divide all there numbers. So we will take one for loop which will start
form min of the numbers and will stop
the loop when it became one, since all numbers are divisible by one.
Inside for loop we will write one if conditions which will check
divisibility of both the numbers.

Program:

**Write a c program for finding gcd (greatest common divisor) of two given numbers**

#include<stdio.h>

int main(){

int x,y,m,i;

printf("Insert
any two number: ");

scanf("%d%d",&x,&y);

if(x>y)

m=y;

else

m=x;

for(i=m;i>=1;i--){

if(x%i==0&&y%i==0){

printf("\nHCF of
two number is : %d",i) ;

break;

}

}

return 0;

}

Other logic :

**HCF (Highest common factor) program with two numbers in c**

#include<stdio.h>

int main(){

int n1,n2;

printf("\nEnter two numbers:");

scanf("%d %d",&n1,&n2);

while(n1!=n2){

if(n1>=n2-1)

n1=n1-n2;

else

n2=n2-n1;

}

printf("\nGCD=%d",n1);

return 0;

}

**HCF program with multiple numbers in c**

#include<stdio.h>

int main(){

int x,y=-1;

printf("Insert
numbers. To exit insert zero: ");

while(1){

scanf("%d",&x);

if(x<1)

break;

else if(y==-1)

y=x;

else if (x<y)

y=gcd(x,y);

else

y=gcd(y,x);

}

printf("GCD is
%d",y);

return 0;

}

int gcd(int x,int y){

int i;

for(i=x;i>=1;i--){

if(x%i==0&&y%i==0){

break;

}

}

return i;

}
## 6 comments:

Hcf of 4 and 8 is 4 not 2.

very helpful nice logic.

thank you.

Very nice and simple logic to find the gcd for multiple numbers. Thanks!

gcd of 4 and 8 is 4 not 2 plzzz correct that. and thank you

gcd of 4 and 8 is 4 not 2 plz correct it

If we know the LCM of two numbers then we can calculate GCD using below expression LCM(A, B) X HCF(A, B) = A*B

## Post a Comment