Sunday, July 8, 2007

Write a C program to find the GCD of two numbers.

Here is a C program ....


#include < stdio.h >

int gcd(int a, int b);
int gcd_recurse(int a, int b);


int main()
{
printf("\nGCD(%2d,%2d) = [%d]", 6,4, gcd(6,4));
printf("\nGCD(%2d,%2d) = [%d]", 4,6, gcd(4,6));
printf("\nGCD(%2d,%2d) = [%d]", 3,17, gcd(3,17));
printf("\nGCD(%2d,%2d) = [%d]", 17,3, gcd(17,3));
printf("\nGCD(%2d,%2d) = [%d]", 1,6, gcd(1,6));
printf("\nGCD(%2d,%2d) = [%d]", 10,1, gcd(10,1));
printf("\nGCD(%2d,%2d) = [%d]", 10,6, gcd(10,6));

printf("\nGCD(%2d,%2d) = [%d]", 6,4, gcd_recurse(6,4));
printf("\nGCD(%2d,%2d) = [%d]", 4,6, gcd_recurse(4,6));
printf("\nGCD(%2d,%2d) = [%d]", 3,17, gcd_recurse(3,17));
printf("\nGCD(%2d,%2d) = [%d]", 17,3, gcd_recurse(17,3));
printf("\nGCD(%2d,%2d) = [%d]", 1,6, gcd_recurse(1,6));
printf("\nGCD(%2d,%2d) = [%d]", 10,1, gcd_recurse(10,1));
printf("\nGCD(%2d,%2d) = [%d]", 10,6, gcd_recurse(10,6));


getch();
getch();
return(0);
}

// Iterative algorithm
int gcd(int a, int b)
{
int temp;

while(b)
{
temp = a % b;
a = b;
b = temp;
}

return(a);
}


// Recursive algorithm
int gcd_recurse(int a, int b)
{
int temp;

temp = a % b;

if (temp == 0)
{
return(b);
}
else
{
return(gcd_recurse(b, temp));
}
}




And here is the output ...


Iterative
----------------
GCD( 6, 4) = [2]
GCD( 4, 6) = [2]
GCD( 3,17) = [1]
GCD(17, 3) = [1]
GCD( 1, 6) = [1]
GCD(10, 1) = [1]
GCD(10, 6) = [2]

Recursive
----------------
GCD( 6, 4) = [2]
GCD( 4, 6) = [2]
GCD( 3,17) = [1]
GCD(17, 3) = [1]
GCD( 1, 6) = [1]
GCD(10, 1) = [1]
GCD(10, 6) = [2]


Note that you should add error handling to check if someone has passed negative numbers and zero.

29 comments:

Sandeep Patra said...

a shorter code

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

Unknown said...

thanks a lot sandeep it actually helped a lot :-)

sushil said...

#include
main()
{
int n,m,a,b,gcd;
printf("\n enter two numbers ");
scanf("%d %d",&a,&b);
n=a;
m=b;
while(n!=m)
{
if(n>m)
n=n-m;
else
m=m-n;
}
gcd=n;

prinf("\n GCD of %d and %d is=%d",a,b,gcd);
}

karthik said...

sandeep your program is wrong i guess it wont work for 9 and 36 because gcd is 9 but 36-9=27

sanz said...

sushil ....thanks....ur program worked....

Unknown said...

nop! sushil ur program didn't work!

Unknown said...

nop! sushil ur program didn't work!

shishir said...

#include
int GCD(int x, int y);
void main() {
int a,b;
scanf("%d/n",&a);
scanf("%d",&b);
printf("the GCD Is:%d", GCD(a,b));

}
int GCD(int x, int y)
{
if(x==y)
return x;
else if (x>y) {
return GCD(x-y,y);
}
else
return GCD(y-x,x);
}

Unknown said...

i meant #include

This should work.
Thanks,
Shishir

Unknown said...

for some reason, the library function is not getting included. please include the standard library function, stdio.h

dhiraj said...

ya! thnx cshir,u gave us the actual prgrm.....thax again.

SHAILY said...

Make a program for finding GCD of two numbers .... then tell!!!

SHAILY said...

Sorry! I meant make a program of finding GCD of two polynomials of degree m,n( m<=n) then tell

Anonymous said...

#include
int gcd(int a,int b);
main()
{
int a,b,i;
scanf("%d %d",&a,&b);
i=gcd(a,b);
printf("%d\n",i);
return 0;
}
int gcd(int a,int b)
{
if(a==0 || a==b)
return b;
if(b==0)
return a;
if(a>b)
return (gcd(a-b,b));
if(b>a)
return (gcd(a,b-a));
}

Anonymous said...

Here's a program showing three different versions, two of which were found here and integrated in


#include

//Checks two numbers and outputs their greatest common divisor
/*
int gcd(int dividend, int divisor)
{
int rem = -1;
while(rem != 0)
{
rem = dividend % divisor;
dividend = divisor;
if(rem != 0)
divisor = rem;
}
}
*/
/*
int gcd(int a, int b)
{
int temp;

while(b)
{
temp = a % b;
a = b;
b = temp;
}

return(a);
}
*/

/*int gcd(int a, int b)
{
int temp;

temp = a % b;

if (temp == 0)
{
return(b);
}
else
{
return(gcd(b, temp));
}*/
}

int main()
{
int a, b;

printf("Enter two numbers: ");

scanf("%i %i", &a, &b);
// if(gcd(a, b) != 1)
printf("GCD = %i \n", gcd(a, b));

}

riya said...

thanks lot. really it makes very helpful to me.

suruchi said...

sushil,your program works .......even it works for 9 nd 36 bt i can,t understand how did it works???
because 36-9=27 bt gcd is 9.it gives 9 bt can u plz tell me how???..

Devanshi gor said...

This really helped me... thanks..

Devanshi gor said...

This really helped me... thanks...

Unknown said...

Use #include

Unknown said...

#include

Unknown said...

Its soo lengthy

Rachumallu said...

ur programme is very easy.if u want effective than this login smart programmers

Rachumallu said...

ur programme is very easy.if u want effective than this login smart programmers

Anonymous said...

Link exchange is nothing else except it is just placing the other
person's blog link on your page at suitable place and other person will also do same in favor of you.

Feel free to visit my web-site: microsoft registry cleaner
My website > registry cleaner

Anonymous said...

This page really has all of the information and facts
I needed concerning this subject and didn't know who to ask.

Look into my web page; http://yearofsocialmedia.net/user/profile/chelseatr/

Anonymous said...

You have made some good points there. I looked on the net for more info about the issue and found most
people will go along with your views on this website.


My weblog ... Besuchen Sie

Anonymous said...

Excellent post. I was checking continuously this blog
and I'm impressed! Very helpful info specially the last part :) I care for such information a lot. I was looking for this certain info for a very long time. Thank you and good luck.

Check out my web site onlineshop schuhe

Anonymous said...

Duperre super-site! I'm loving it! ' Will come back again - take
it to eat, thank you.

my web blog - affiliate marketplace sites :: ::