# Is my code for gcd function valid?

1. May 28, 2007

### MathematicalPhysicist

i have to write the function gcd for c programme.
here's my code:
Code (Text):

int gcd(int m, int n)
{
int s,r,x,y;

if (m>=n)
{
r=m-(m/n)*n;
for(x=m,y=n;r!=0;x=y,y=r)
r=x-(x/y)*y;
}
if(n>m)
{
r=n-(n/m)*n;
for(x=n,y=m;r!=0;x=y,y=r)
r=x-(x/y)*y;
}
return(r);
}

so is this correct? im using the fact that the divison of two integers returns an integer solution, i.e without the remainder, and ofcourse euclid's algorithm.
p.s
this is a part of a programme that i need to do in order to check for pythaogrean triplets, so it's not supposed to run alone.

thanks in advance.

2. May 28, 2007

### MathematicalPhysicist

Code (Text):
int gcd(int m, int n)
{
int s,r,x,y;

if (m>=n)
{
r=m-(m/n)*n;
for(x=m,y=n;r!=0;x=y,y=r)
{
s=r;
r=x-(x/y)*y;
}
}
if(n>m)
{
r=n-(n/m)*n;
for(x=n,y=m;r!=0;x=y,y=r)
{
s=r;
r=x-(x/y)*y;
}
}
return(s);
}

i think that now it works ok, what do you think?

3. May 29, 2007

### ranger

Yea, its working. But you need to add a case that covers when there is no remainder. Like when I do 10 and 5, the program returns 0 as the gcd.

Heres a stand alone program that I wrote, utilizing the modulus function.
Code (Text):

/ * Euclid's method of finding the greatest common divisor of two integers*/
#include <stdio.h>

int gcd(int num1, int num2);
int swap(int *pa, int *pb);

int main()
{
int m,n,gcd_num;

printf("Enter two integers\n");
scanf("%d %d", &m, &n);
if(m <= 0 || n <= 0) {
printf("Zero input detected\n");
exit(1);
}
if(m <= n) swap(&m, &n);
gcd_num = gcd(m,n);
printf("\nThe greatest common divisor of %d and %d is %d\n",m,n,gcd_num);
return 0;
}

int swap(int *pa, int *pb)
{
int temp = *pa;
*pa = *pb;
*pb = temp;
return;
}

int gcd(int m, int n)
{
int r;

[b]if(m%n == 0)
r = n;[/b]

while((m%n!=0))
{
r = m%n;
printf("Trying %d\n",r);
m=n;
n=r;
}
return r;
}

The bold lines takes care of the case when there is no remainder.

Last edited: May 29, 2007
4. May 30, 2007

### MathematicalPhysicist

now i need to write a programme that will get as input, 'n' and 'max' it should look on triples such that 1<=a<b<c<=max and check wether they satisfy a^n+b^n=c^n, if so the triple will be printed, and at the end there will be printed the number of triples.
i need no duplicates of triples such as: 3,4,5 or 4,3,5 which are the same and that gcd(a,b)=1.
now he i wrote the programme, but im finding difficult where to put the condition that a<b<c, here's what i did so far:
Code (Text):

#include <stdio.h>
int gcd(int m,int n)
{
int r,s,x,y;
if(m>=n){
r=m-(m/n)*n;
if(r==0)
s=n;
for(x=m,y=n;r!=0;x=y,y=r)
{
s=r;
r=x-(x/y)*y;
}

}
if(n>m){
r=n-(n/m)*m;
if(r==0)
s=m;
for(x=m,y=n;r!=0;x=y,y=r)
{
s=r;
r=x-(x/y)*y;
}
}
return(s);
}
int pow(int a, int t)
{
int q,p;
for(p=1,q=1;q<=t;q++)
p=a*p;

return(p);
}
main()
{
int d,f=0,n,max,a,b,c;
printf("insert the degree you wish to check for n-th pythogrean triplets\n");
scanf("%d", &n);
printf("insert the maximal number you want to check for\n");
scanf("%d", &max);
if(max>2){

for(a=1;a<=max;a++)
{
for(b=2;b<=max;b++)
{
for(c=3;a<b,b<c,c<=max;c++)
{
if((pow(a,n)+pow(b,n)==pow(c,n))&& gcd(a,b)==1){
f++;
printf("the triplet is: %d, %d, %d \n", a,b,c);
}
if(pow(a,n)+pow(b,n)==pow(c,n)&& (gcd(a,b))!=1){
f++;
printf("the triplet is: %f, %f, %f \n", a/(gcd(a,b)),b/(gcd(a,b)),c/(gcd(a,b)));
}
}
}
}
}

if(max<=2)
printf("there isn't such triplet \n");
printf("the number of triplets in the specified domain is: %d \n", f);
}

any hints where should i put this condition, i put it in the third loop, but it doesnt seem to work.
your help is appreciated.

5. Jun 1, 2007

### MathematicalPhysicist

here's an abbreviated code, without specifting the gcd and pow functions:
Code (Text):

int d,f=0,n,max,a,b,c;
printf("insert the degree you wish to check for n-th pythogrean triplets\n");
scanf("%d", &n);
printf("insert the maximal number you want to check for\n");
scanf("%d", &max);
if(max>2){

for(a=1;a<=max;a++)
{
for(b=2;b<=max;b++)
{
for(c=3;a<b,b<c,c<=max;c++)
{
if((pow(a,n)+pow(b,n)==pow(c,n))&& gcd(a,b)==1){
f++;
printf("the triplet is: %d, %d, %d \n", a,b,c);
}
if(pow(a,n)+pow(b,n)==pow(c,n)&& (gcd(a,b))!=1){
f++;
printf("the triplet is: %f, %f, %f \n", a/(gcd(a,b)),b/(gcd(a,b)),c/(gcd(a,b)));
}
}
}
}
}

if(max<=2)
printf("there isn't such triplet \n");
printf("the number of triplets in the specified domain is: %d \n", f);
}

i hope someone can give me some hint.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?