## INDEX

### Find g.c.d of two number using c program

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;
}

1. 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

2. Excellent logic i got it

3. Excellent Good Try

and i want gcd for more than two numbers if any one knows please explain

2. /*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;
}

3. /*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;
}

4. above is for finding gcd of 3 numbers

4. 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;

}

1. rare...........!!!!!!!!!

2. 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

5. 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.

6. nice

7. iam not able to understand the real logic behind this .pls send stepby step solution to find the hcf of two numbers ......

8. gcd of two numbers using recurssive function?
if ne one knws plz post

9. while(y!=0)
temp=x%y;
x=y;
y=temp;

gcd logic correct r not

10. printf("THANQ VERY MUCH");

(-.-)

11. 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();

}

12. #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;

}

1. pleaz the directives are stdio.h and stdlib.h i will be glad with any reasonable criticism

13. thank you very much.

14. can any one plz write a c program to find minimal or conical cover of functional dependency >>>?

15. sorry

16. Thanks.

17. 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? ;)

1. by Euclid method

18. Hi Siddharth Great Job!!!

19. @komal
Bhai apna logic samjhao toh yaar...
Incomprehensible...

20. Very nice and simple and super by cquestions

21. 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,?,?

22. #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();
}

23. #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);
}

24. 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.

25. 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);

}

1. 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);

26. 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);
}

27. #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();
}

28. @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.

29. great job guys

30. hcf of 4 and 8 is 4 and not 2

31. Khyati Thakkar11/13/13, 2:40 AM

Int GCD(int m,int n)
{
If (m<n)
return (GCD(n,m));
If (m%n==0)
return (n);
return(GCD(n,m%n));
}

32. write a program to withdraw money in atm

33. Recursion one is good

34. 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.

35. 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).

36. what i do for last line?

37. Your "other HCF logic" has bug it wont work properly for (5,3)

38. #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);
}

39. int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}

40. /* 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
------------------------------*/

41. 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?

42. Thanks Alot...
It's my exercise question and it helped me alot...

43. write a c programming to find the gcd of numbers of array,, please give me the solution :(

44. write a c programming to find the gcd of numbers of array,, please give me the solution :(

1. This comment has been removed by the author.

45. This comment has been removed by the author.

46. This comment has been removed by the author.

47. #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);
}

48. please write a programme on GCD using pointers

49. 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);
}
}

50. #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*/

51. #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*/