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.
a shorter code
ReplyDeleteint 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 :-)
ReplyDelete#include
ReplyDeletemain()
{
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
ReplyDeletesushil ....thanks....ur program worked....
ReplyDeletenop! sushil ur program didn't work!
ReplyDeletenop! sushil ur program didn't work!
ReplyDelete#include
ReplyDeleteint 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
ReplyDeleteThis should work.
Thanks,
Shishir
for some reason, the library function is not getting included. please include the standard library function, stdio.h
ReplyDeleteya! thnx cshir,u gave us the actual prgrm.....thax again.
ReplyDeleteMake a program for finding GCD of two numbers .... then tell!!!
ReplyDeleteSorry! I meant make a program of finding GCD of two polynomials of degree m,n( m<=n) then tell
ReplyDelete#include
ReplyDeleteint 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
ReplyDelete#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));
}
Its soo lengthy
Deletethanks lot. really it makes very helpful to me.
ReplyDeletesushil,your program works .......even it works for 9 nd 36 bt i can,t understand how did it works???
ReplyDeletebecause 36-9=27 bt gcd is 9.it gives 9 bt can u plz tell me how???..
This really helped me... thanks..
ReplyDeleteThis really helped me... thanks...
ReplyDeleteUse #include
ReplyDelete#include
ReplyDeleteur programme is very easy.if u want effective than this login smart programmers
ReplyDeleteur programme is very easy.if u want effective than this login smart programmers
ReplyDeleteLink exchange is nothing else except it is just placing the other
ReplyDeleteperson'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
This page really has all of the information and facts
ReplyDeleteI 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
ReplyDeletepeople will go along with your views on this website.
My weblog ... Besuchen Sie
Excellent post. I was checking continuously this blog
ReplyDeleteand 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
Duperre super-site! I'm loving it! ' Will come back again - take
ReplyDeleteit to eat, thank you.
my web blog - affiliate marketplace sites :: ::