Definition
of HCF (Highest
common factor):
HFC is also 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 two numbers 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;
}
65 comments:
im finding solution for this programme since 5days.now i got the logic but better to explain the programme in theriotically please.its reaaly need for basic learner like me.
regard
geeta
Excellent logic i got it
Excellent Good Try
and i want gcd for more than two numbers if any one knows please explain
gcd of 3 numbers with high efficiency
#include
int gcd(int , int , int);
int main()
{
int i , j , k , g;
scanf("%d %d %d", &i , &j , &k);
g = gcd(i , j , k);
printf("%d",g);
return 0;
}
int gcd(int i , int j , int k)
{
int least;
least = i;
while(!( (i == j) && (j == k) ) )
{
i = (i == 0 ? least : i);
j = (j == 0 ? least : j);
k = (k == 0 ? least : k);
if(i <= j)
{
if(i <= k)
least = i;
else
least = k;
}
else
{
if(j <= k)
least = j;
else
least = k;
}
i = i % least;
j = j % least;
k = k % least;
}
return least;
}
In "Other logic : HCF program with two numbers in c"- In the first if statement condition n1>=n2-1,
here "-1" is redundant. I think.
nice
iam not able to understand the real logic behind this .pls send stepby step solution to find the hcf of two numbers ......
gcd of two numbers using recurssive function?
if ne one knws plz post
while(y!=0)
temp=x%y;
x=y;
y=temp;
gcd logic correct r not
printf("THANQ VERY MUCH");
(-.-)
The Logic is simple...i used array ...it is not necessary...just to explain how it works...the output shows the step by step procedure to find hcf
#include
void main()
{
int x,y,f1[100],f2[100],c[1000],i,j,k,l,m,n;
printf("\ninput the 2 numbers whose hcf is to be found\n");
scanf("%d%d",&x,&y);
for(j=0,i=1;i<=x/2;i++)
{
if(x%i==0)
{
f1[j]=i;
j++;
}
}
f1[j]=x;
j++;
for(k=0,i=1;i<=y/2;i++)
{
if(y%i==0)
{
f2[k]=i;
k++;
}
}
f2[k]=y;
k++;
printf("\nfactors of first number\n");
for(i=0;i<j;i++)
{ printf("%d ",f1[i]);
}
printf("\nfactors of second number\n");
for(i=0;i<k;i++)
{ printf("%d ",f2[i]);
}
for(m=0,i=0;i<j;i++)
{
for(n=0;n<k;n++)
{
if(f1[i]==f2[n])
{
c[m]=f1[i];
m++;
}
}
}
printf("\nCommon factors\n");
for(i=0;i<m;i++)
printf("%d ",c[i]);
printf("\nGCD (Greatest Common Factor): %d \n",c[i-1]);
printf("\nLCM (Least Common Factor: ");
if(c[1]=='\0')
printf("%d",c[0]);
else
printf("%d",c[1]);
getch();
}
#include
#include
int GCD(int x, int y);
int main()
{
int x;
int y;
int z;
printf("Enter the two digits you wich to look for their common difference \n");
scanf("%d%d \n", &x , &y );
printf("The Greatest common divisor: %d\n", GCD(x , y));
return 0;
}
/* the definition of the function greatest common divisor*/
int GCD(int x, int y)
{
int z;
if( (int) (x*y)/2 == z);
return (x*y)/2;
}
pleaz the directives are stdio.h and stdlib.h i will be glad with any reasonable criticism
thank you very much.
can any one plz write a c program to find minimal or conical cover of functional dependency >>>?
sorry
Thanks.
Really helpful for me .
I got a much easier logic than this..
Suppose a=16, b=12:
then while (r!=0)
a%b=r;
a=b;
b=r;
What say? ;)
Hi Siddharth Great Job!!!
@komal
Bhai apna logic samjhao toh yaar...
Incomprehensible...
Very nice and simple and super by cquestions
print the next two number and use only one variable for each question
a)0,5,10,15,20,25,?,?
b)0,2,4,6,8,10,?,?
c)1,2,4,8,16,32,?,?
who can help me..please.....
#include
#include
voidmain()
{
int a,b,n,m,gcd;
clrscr();
printf("enter the valuse of a,b");
scanf("%d%d",&a,&b);
n=a;
m=b;
while(n!=m)
{
if(n>m)
n=n-m
else
m=m-n
}
gcd=n;
printf("gcd of %d and %d is %d",a,b,gcd);
getch();
}
#include
#include
void main()
{
int a,b,c;
printf("Enter 2 digit:");
scanf("%d%d",&a,&b);
while(a%b!=0)
{
c=a%b;
a=b;
b=c;
}
printf("GCD is %d",b);
}
Sir plzz solve this problem...
Euclid's Algorithm is a well-known algorithm for computing the greatest common divisor (GCD) of two numbers.
The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation
GCD (a, b) = GCD (b, r)
to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,
GCD (36, 20) = GCD (20, 16) = GCD (16, 4) = GCD (4, 0) = 4
Implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair.
Write a method named gcd that computes the greatest common divisor of two integers. Add some code to main that tests the new method.
Use Euclidean Algorithm of NUMBER THEORY , best solution .....
#include
main()
{
int a,b,gcd,temp,a1,b1; /* we need to make a>b */
printf("Enter two numbers a and b \n");
scanf("%d%d",&a,&b);
a1=a; b1=b;
if(a<b)
{ temp=a;
a=b;
b=temp; }
while((a%b)!=0)
{
temp=a%b;
a=b;
b=temp;
}
gcd=temp;
printf("The GCD of %d and %d is %d\n",a1,b1,gcd);
}
This is how Euclidean Algorithm Work.
In this we take two numbers a and b (a>b) and we need to find the gcd of them.
So first we apply division algorithm a=q1*b+r1 if r1=0 then b/a and gcd(a,b)=b else we divide b by r1 i.e. b=q2*r1 + r2; and if r2=0 gcd=r1 else r1=q3*r2+r3
and continue in similar fashion we get
r_n-2=q_n*r_n-1+r_n;
r_n-1=q_n+1*r_n +0;
so gcd(a,b)=r_n using if a=bq+r;
gcd(a,b)=gcd(b,r);
Euclid's algorithm based program to find gcd of two number.
#include
main()
{
int a, b, temp;
scanf("%d %d", &a, &b);
while(b)
{
temp = b;
b = a%b;
a = temp;
}
printf("%d", a);
}
thks frnd
#include
#include
int main()
{
int m,n,gcd,r;
printf("enter the first number");
scanf("%d",&m);
printf("enter the second number");
scanf("%d",&n);
while(m%n!=0)
{
r=m%n;
m=n;
n=r;
}
gcd=n;
printf("greatest common divisor of m and n is %d",gcd);
return 0;
getch();
}
@admin - The statement in the starting saying
"For example HCF of two numbers 4 and 8 is 2 since 2 is the largest positive number which can dived 4 as well as 8 without a remainder. "
is wrong. HCF of 4 and 8 is 4.
great job guys
hcf of 4 and 8 is 4 and not 2
rare...........!!!!!!!!!
Int GCD(int m,int n)
{
If (m<n)
return (GCD(n,m));
If (m%n==0)
return (n);
return(GCD(n,m%n));
}
write a program to withdraw money in atm
NICE WORK
Recursion one is good
if(x>y)
m=y;
else
m=x;
isnt required because the gcd of two number is always equal to or lesser than least number of given two numbers.
for example:
111 and 666 are given as two inputs then the gcd will either equal to 111 or less than it,here gcd is 111.so assign m as any one of the two inputs "i" in the for loop will definitely come to 111 and may go below it in other examples.
hai
Greatest Common Divisor (GCD) of two integers a and b, denoted by gcd(a,b), is the greatest integer dividing both a and b. For example gcd(8,4) = 4, gcd(5,7) = 1, gcd(9,3)=3 etc. Write down a program that will take two integers as input and will calculate the GCD of two using loop. Draw a table showing values of each variables in every step of the loop for gcd(32,12).
what i do for last line?
Your "other HCF logic" has bug it wont work properly for (5,3)
#include
main()
{
int n1,n2,n3;
scanf("%d %d",&n1 &n2);
n3=gcd(n1,n2);
printf("GCD of %d & %d =%d\n",n1,n2,n3);
}
int gcd(int i,int j);
{
int temp;
if(i<j)
{
temp=i;
i=j;
j=temp;
}
while(i%j!=0)
{
temp=i%j;
i=j;
j=temp;
}
return(j);
}
really encouraging but some of the c programs posted here need to be edited for them to give the right answer rhyming with what we know!!!!! other wise guys you are doing marvelous
int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}
try on your own
/*To find GCD of two given numbers*/
/*File inclusion*/
#include
#include
main()
{
int a,b,c,d,f=0;
clrscr();
printf("To find GCD, please enter the two numbers..\n");
scanf("%d %d",&a,&b);
if(a<b)
{
c=a; /*This if-else condition will take least value among the two values a and b*/
}
else
{
c=b;
}
printf("%d and %d are divisible by:\n",a,b);
for(d=1;d<=c;d++)
{
if(a%d==0 && b%d==0)
{
printf("%d ",d);
if(f<d)
{
f=d;
}
}
}
printf("\n\nThe GCD is...%d",f);
getch();
return;
}
-Answer from INDIA
/*To find GCD of two given numbers*/
/*File inclusion*/
#include
#include
main()
{
int a,b,c,d,e,f=0;
clrscr();
printf("To find GCD, please enter the two numbers..\n");
scanf("%d %d %d",&a,&b,&e);
if(a<b)
{
if(a<e)
{
c=a; /*This if-else condition will take least value among the three values a , b and e*/
}
else
{
c=e;
}
}
else
{
if(b<e)
{
c=b;
}
else
{
c=e;
}
}
printf("%d , %d and %d are divisible by:\n",a,b,e);
for(d=1;d<=c;d++)
{
if(a%d==0 && b%d==0 && e%d==0)
{
printf("%d ",d);
if(f<d)
{
f=d;
}
}
}
printf("\n\nThe GCD is...%d",f);
getch();
return;
}
-Answer from INDIA
above is for finding gcd of 3 numbers
/* Write a C program to find the GCD and LCM of two integers *
* output the results along with the given integers. Use Euclids' algorithm*/
#include
#include
void main()
{
int num1, num2, gcd, lcm, remainder, numerator, denominator;
clrscr();
printf("Enter two numbers\n");
scanf("%d %d", &num1,&num2);
if (num1 > num2)
{
numerator = num1;
denominator = num2;
}
else
{
numerator = num2;
denominator = num1;
}
remainder = num1 % num2;
while(remainder !=0)
{
numerator = denominator;
denominator = remainder;
remainder = numerator % denominator;
}
gcd = denominator;
lcm = num1 * num2 / gcd;
printf("GCD of %d and %d = %d \n", num1,num2,gcd);
printf("LCM of %d and %d = %d \n", num1,num2,lcm);
} /* End of main() */
/*------------------------
Output
RUN 1
Enter two numbers
5
15
GCD of 5 and 15 = 5
LCM of 5 and 15 = 15
------------------------------*/
Can anyone tell me how i calculate the gcd of two large numbers which is out of range.....like gcd of this two numbers:682482586846258649865984699439696946936986986986539486948679374 and 6453658639862598643985643695693886549236598643956952969......can anyone answer it?
by Euclid method
Thanks Alot...
It's my exercise question and it helped me alot...
Thank you.. May Allah guide help you..
write a c programming to find the gcd of numbers of array,, please give me the solution :(
write a c programming to find the gcd of numbers of array,, please give me the solution :(
#include
#include
void main()
{
int n1,n2,gcd;
printf("Enter numbers:\n");
scanf("%d %d",&n1,&n2);
if(n1>n2&&n1!=0&&n2!=0)
{
gcd=(n1%n2);
}
else if(n2>n1&&n2!=0&&n1!=0)
{
gcd=(n2%n1);
}
else if(n1==0)
{
gcd=n2;
}
else
{
gcd=n1;
}
printf("GCD of %d and %d is %d",n1,n2,gcd);
}
please write a programme on GCD using pointers
int gcd(int num1,int num2)
{
int greater,smaller,remainder;
if(num1>num2)
{
greater = num1;
smaller = num2;
}
else
{
greater = num2;
smaller = num1;
}
remainder = num1%num2;
if(remainder==0)
{
return smaller;
}
else
{
gcd(smaller,greater%smaller);
}
}
#include
int main()
{
int a,b,c,m,i;
printf("enter a,b,c values:");
scanf("%d%d%d",&a,&b,&c);
(a>b&&a>c)?m=a:b;
(b>c)?(m=b):(m=c);
for(i=m;i>=1;i--){
if(a%i==0&&b%i==0&&c%i==0){
printf("\nHCF or GCD of three numbers is : %d",i) ;
break;
}
}
return 0;
}
/*OUTPUT
enter a,b,c values:9,27,81
HCF or GCD of three numbers is:9*/
#include
int main()
{
int a,b,c,m,i;
printf("enter a,b,c values:");
scanf("%d%d%d",&a,&b,&c);
(a>b&&a>c)?m=a:b;
(b>c)?(m=b):(m=c);
for(i=m;i>=1;i--){
if(a%i==0&&b%i==0&&c%i==0){
printf("\nHCF or GCD of three numbers is : %d",i) ;
break;
}
}
return 0;
}
/*OUTPUT
enter a,b,c values:9,27,81
HCF or GCD of three numbers is:9*/
Recursion By Kyati is very impressive. Helped me. Thanks.
Post a Comment