1

標準の GCD アルゴリズムを使用せずに、与えられた 2 つの数値が互いに素であるかどうかを知ることは可能ですか?ユークリッド、バイナリ GCD、レーマーのアルゴリズムを使用しました。可能であれば、これらよりも高速な方法を提案してください。2 つの数値は 10^5 まで大きくなる可能性があるため、Faray シーケンスを生成しても役に立ちません。

4

1 に答える 1

3

これら 2 つの単純な実装のいずれかが、コメントでリンクした関数よりも高速に見つかる場合があります。これは c# コードですが、c または Java に簡単に変換できるはずです。これらは unsigned int を対象としていますが、別の型のバージョンを作成するのは簡単です。

public static uint Gcd(uint value1, uint value2) {
    while (value1 != 0) {
        uint t = value2 % value1;
        value2 = value1;
        value1 = t;
    }
    return value2;
}

public static uint GcdR(uint value1, uint value2) {
    return (value1 == 0) ? value2 : GcdR(value2 % value1, value1);
}

モジュロ演算子のために遅くなるようですが、少なくともC＃では、リンクした関数の2倍以上高速です（C＃に変換した後）。最初の非再帰バージョンの方がわずかに速いことがわかりました。使用している言語について、ベンチマークを実行して、どちらかが現在のものよりも高速かどうかを確認する必要があります。Gcdを使ったIsCoprimeはこんな感じ

public static bool IsCoprime(this uint value1, uint value2) {
    // 25% of possible pairings are even num to even num so handle them
    // with a bit twiddle that's much faster than GCD function. If they
    // are both even, then they can't be coprime (2 is common divisor).
    return ((((value1 | value2) & 1) != 0)
            && (Gcd(value1, value2) == 1));
}
于 2014-03-14T22:48:09.417 に答える