c - 相对质检？

Question

好的，所以相对素数意味着两个数没有大于 1 的公因数。它也可以看作是 gcd = 1 的两个数。

因此，沿着这些思路，这是我编写的用于查找两个相对素数 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);

gcd 函数定义为：

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

当我设置时z = 60，我得到的 e 是e= 0 ......实际上我一直得到与初始化 for 循环相同的e

我究竟做错了什么？有没有其他方法可以判断两个数是否互质？

编辑：

好的，根据 minitech 的建议，这里是修改后的代码：

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

现在，当我设置 z=60 时，我的 e 变成了 e = 60，这又是错误的。正确答案应该是 e = 7

score 1 · Accepted Answer

修复之后，你总是会得到 1，因为它对所有东西都是质数。z - 1如果您想要最大的，请尝试从开始并减少。你也应该只是break;而不是保持一个标志。

score 1 · Accepted Answer

这有点脆弱，因为它无法处理零参数；例如，

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

我会选择类似的东西：

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

我使用无符号类型，因为没有理由使用负参数——它们不会影响 gcd 的结果，它总是非负的。

2 回答 2