Relatively prime check?

Question

Ok so relatively prime means that two numbers have no common factors greater than 1. It can also be viewed as two numbers that have gcd = 1.

So along those lines, this is the code i wrote to find two relatively prime numbers e,z :

for(e = 0,flag=0; (flag==1); e++){ 
    if( gcd( e, z ) == 1){   // z in this example is 60
        flag = 1;
    } 
}

printf("e = %d\n",e);

and the gcd function is defined as :

int gcd(int i, int x){
   if(x % i == 0) return( i );
   return( gcd( x % i, x ) );
}

when I set z = 60, the e I get is e= 0 ... Actually I keep getting the same e with which I initialize the for loop

What am I doing wrong? Is there any other way of finding if two numbers are relatively prime?

EDIT:

Ok as per the suggestion from minitech here is the modified code:

for(e = 2,flag=0; !flag; e++){
    if( gcd( e, z ) == 1){
        flag = 1;
    } 
}

now when I set my z=60 , my e is coming out to be e = 60 which is again wrong. Correct answer should be e = 7

Answer 1

• You shouldn’t start at zero
• Your flag condition should be !flag

After fixing that, you will always get 1, because it’s relatively prime to everything. Try starting at z - 1 and decrementing if you want the biggest one. You should also just break; instead of keeping a flag.

Answer 2

This is a little fragile, since it can't handle a zero argument; e.g.,

gcd(z, z) = gcd(z, 0) = gcd(0, z) = |z|.

I'd go with something like:

unsigned gcd (unsigned u, unsigned v)
{
    unsigned t;
    for (; (t = v) != 0; u = t)
        v = u % v;
    return u;
}

I use unsigned types, because there's no reason to use negative arguments - they don't affect the result of a gcd, which is always non-negative.