1

私はウィキペディアからアルゴリズムを実装しようとしてきましたが、素数として合成数を出力することはありませんが、素数の75％を合成数として出力しています。

1000までは、素数のこの出力を提供します。

3、5、7、11、13、17、41、97、193、257、641、769

私の知る限り、私の実装は擬似コードアルゴリズムとまったく同じです。私はそれを行ごとにデバッグし、期待されるすべての変数値を生成しました（私は計算機と一緒にフォローしていました）。これが私の関数です：

bool primeTest(int n)
{
    int s = 0;
    int d = n - 1;

    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }

    // this is the LOOP from the pseudo-algorithm
    for (int i = 0; i < 10; i++)
    {
        int range = n - 4;
        int a = rand() % range + 2;
        //int a = rand() % (n/2 - 2) + 2;
        bool skip = false;
        long x = long(pow(a, d)) % n;

        if (x == 1 || x == n - 1)
            continue;

        for (int r = 1; r < s; r++)
        {
            x = long(pow(x, 2)) % n;

            if (x == 1)
            {
                // is not prime
                return false;
            }
            else if (x == n - 1)
            {
                skip = true;
                break;
            }
        }

        if (!skip)
        {
            // is not prime
            return false;
        }
    }

    // is prime
    return true;
}

助けていただければ幸いですD：

編集：これがあなたたちが提案したように編集されたプログラム全体です-そして今、出力はさらに壊れています：

bool primeTest(int n);

int main()
{
    int count = 1;     // number of found primes, 2 being the first of course
    int maxCount = 10001;
    long n = 3;
    long maxN = 1000;
    long prime = 0;

    while (count < maxCount && n <= maxN)
    {
        if (primeTest(n))
        {
            prime = n;
            cout << prime << endl;
            count++;
        }

        n += 2;
    }

    //cout << prime;
    return 0;
}

bool primeTest(int n)
{
    int s = 0;
    int d = n - 1;

    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }

    for (int i = 0; i < 10; i++)
    {
        int range = n - 4;
        int a = rand() % range + 2;
        //int a = rand() % (n/2 - 2) + 2;
        bool skip = false;
        //long x = long(pow(a, d)) % n;
        long x = a;
        for (int z = 1; z < d; z++)
        {
            x *= x;
        }

        x = x % n;

        if (x == 1 || x == n - 1)
            continue;

        for (int r = 1; r < s; r++)
        {
            //x = long(pow(x, 2)) % n;
            x = (x * x) % n;

            if (x == 1)
            {
                return false;
            }
            else if (x == n - 1)
            {
                skip = true;
                break;
            }
        }

        if (!skip)
        {
            return false;
        }
    }

    return true;
}

これで、（以前のように）3から1000までの素数の出力は次のようになります。

3、5、17、257

xが大きくなりすぎて、ごみの値になってしまうことがわかりましたが、「％n」の部分を削除するまで、それはわかりませんでした。

4

2 に答える 2

3

エラーの原因として考えられるのは、pow関数への2回の呼び出しです。中間結果は（特に最初の呼び出しでは）巨大になり、おそらくオーバーフローしてエラーが発生します。ウィキペディアでべき乗剰余のトピックを確認する必要があります。

于 2012-09-14T20:49:21.573 に答える
2

問題の原因はおそらくここにあります：

x = long(pow(x, 2)) % n;

powCの標準ライブラリは浮動小数点数で動作するため、nを法とする累乗を計算するだけの場合は、これを使用することは非常に悪い考えです。解決策は本当に簡単です。手で数を二乗するだけです。

x = (x * x) % n
于 2012-09-14T20:41:00.663 に答える