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.

## Sunday, July 8, 2007

Subscribe to:
Post Comments (Atom)

## 30 comments:

a shorter code

int gcd (int a, int b) {

if(b == 0) {

return a;

} else {

return (gcd (b, a%b));

}

}

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

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

}

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

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

nop! sushil ur program didn't work!

nop! sushil ur program didn't work!

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

}

i meant #include

This should work.

Thanks,

Shishir

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

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

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

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

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

}

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

}

thanks lot. really it makes very helpful to me.

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

This really helped me... thanks..

This really helped me... thanks...

Use #include

#include

Its soo lengthy

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

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

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

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

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

Appreciation for nice Updates, I found something new and folks can get useful info about BEST ONLINE TRAINING

Duperre super-site! I'm loving it! ' Will come back again - take

it to eat, thank you.

my web blog - affiliate marketplace sites :: ::

Post a Comment