c - 比較的プライムチェック？

Question

互いに素であるということは、2 つの数が 1 より大きい公約数を持たないことを意味します。また、gcd = 1 を持つ 2 つの数と見なすこともできます。

したがって、これらの行に沿って、これは2つの互いに素な数 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を取得し続けます

私は何を間違っていますか？2 つの数が互いに素であるかどうかを調べる方法はありますか?

編集：

ミニテックからの提案によると、変更されたコードは次のとおりです。

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