c++ - このランダム化された素数性テスト アルゴリズムの複雑さを改善するにはどうすればよいですか?

Question

素数の場合は 1 を返し、合成数の場合は 0 を返す次のプログラムを作成しました。コンポジットを素数として誤って識別する可能性はありますが、次のアルゴリズムの時間の複雑さを改善 (減少) するための提案が必要です。

int compute(int n)
{
    int x;
    for(int i = 1; i < 100 * sqrt(n); i++)
    {
        x = rand() % ((int)sqrt(n) + 1);
        if(x != 0 && x != 1 && x!=n)
        {
            if(n % x == 0)
            return 0;
        }
    }
    return 1;
}

Answer 1

Miller-Rabin primality test をご覧ください。このテストでは、一連の「証人」値を使用して、いくつかの計算を実行します。各証人計算は、「複合」または「おそらく素数」の結果をもたらします。k 人の証人を使用し、それらすべてが「おそらく素数」の結果を出す場合、その数が実際に合成される確率は 1/4^k です。

ランタイムは O(k log^3 n) で、これは O(sqrt(n)) アルゴリズムより大幅に改善されています。