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


65 comments:

Anonymous said...

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

Anonymous said...

Excellent logic i got it

Anonymous said...

Excellent Good Try

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

Kamal said...

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;

}

Anonymous said...

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.

Anonymous said...

nice

Anonymous said...

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

Anonymous said...

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

raj said...

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

gcd logic correct r not

Anonymous said...

printf("THANQ VERY MUCH");

(-.-)

Rahul said...

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

}

blissmen said...

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

}

blissmen said...

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

sudhir rajput said...

thank you very much.

Arjun said...

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

Anonymous said...

sorry

Jyotsna said...

Thanks.
Really helpful for me .

Siddhartha Rao said...

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

Priyanka kumari said...

Hi Siddharth Great Job!!!

Anonymous said...

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

Anonymous said...

Very nice and simple and super by cquestions

Anonymous said...

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

Unknown said...

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

Anonymous said...

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

Unknown said...

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.

ANKIT KAMBOJ said...

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

}

ANKIT KAMBOJ said...

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

Anand said...

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

Unknown said...

thks frnd

Unknown said...

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

Shreyans Gandhi said...

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

Rashid said...

great job guys

Anonymous said...

hcf of 4 and 8 is 4 and not 2

Anonymous said...

rare...........!!!!!!!!!

Khyati Thakkar said...

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

Anonymous said...

write a program to withdraw money in atm

Anonymous said...

NICE WORK

Anonymous said...

Recursion one is good

Unknown said...

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.

Unknown said...

hai

Unknown said...

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

Unknown said...

what i do for last line?

Unknown said...

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

Unknown said...

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

Anonymous said...

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

Unknown said...

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

Anonymous said...

try on your own

Anonymous said...

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

Anonymous said...

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

Anonymous said...

above is for finding gcd of 3 numbers

Unknown said...

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

Unknown said...

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?

Unknown said...

by Euclid method

Unknown said...

Thanks Alot...
It's my exercise question and it helped me alot...
Thank you.. May Allah guide help you..

Unknown said...

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

Unknown said...

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

Unknown said...
This comment has been removed by the author.
Unknown said...
This comment has been removed by the author.
Unknown said...
This comment has been removed by the author.
Unknown said...

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

nikhitha said...

please write a programme on GCD using pointers

Unknown said...

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

Unknown said...

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

Unknown said...

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

SugusBlog said...

Recursion By Kyati is very impressive. Helped me. Thanks.