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.