0

現在、私はすべての素数を計算したいプロジェクトに取り組んでいます。(MINGW Windows Comp.) をコンパイルすると、プログラムがクラッシュし、ランダムなエラー番号が返されます。これは私が書いたコードです:

http://pastebin.com/4vVnAM2v

/*
    Sieb des Eratosthenes
*/

#include <iostream>
#include <math.h>
using namespace std;

main()
{
    //variablendeklaration
    unsigned int nmax=100;
    unsigned int i,j,erg;
    bool prim[nmax];

    //Initialisieren
    prim[0]=false;
    prim[1]=false;

    //array prim[i] erstellen
    for(i=2;i<nmax;i++)
    {
        prim[i]=true;
    }




    for(i=2;i<nmax;i++) //alle Primzahlen durchlaufen
    {
        if(prim[i] == true) //auf Prim prüfen
        {
            for(j=2;j<nmax;j++) //multiplizieren und wegstreichen
            {
                erg = j * i;
                prim[erg] = false;
            }
        }
    }

    for(i=2;i<nmax;i++)
    {
        cout << prim[i] << endl;
    }


}
4

2 に答える 2

1

この問題を解決する別の方法は、ループ内の余分なステップを避けることです。

for(i=2; i < nmax; i++)
{
    if(prim[i] == true)
    {
        for (j = 2 * i; j < nmax; j += i) // state j at 2i, increment by i
        {
            prim[j] = false;
        }
    }
}

これには、1）nmaxネストされたアイテムをループしないという効果があります（全体的な複雑さを O(n^2) から O(n * (n/2 + n/6 + n/10 + ...) に減らします。これは事実上 O です） (n log n)、および 2) ループ状態で範囲外になることはないため、追加の境界チェックは必要ありません。

于 2013-10-03T19:26:04.127 に答える
1

この時点で：

            erg = j * i;
            prim[erg] = false;

とのprim両方が までの値を持つことができるため、最終的に の境界を超えてアクセスすることになるため、最大値は になります。この条件をチェックし、次の場合にブレークする必要があります。ijnmax - 1erg(nmax - 1) * (nmax - 1)erg >= nmax

            erg = j * i;
            if (erg < nmax)          // if i * j still within bounds
                prim[erg] = false;   // set prim[i * j] to false
            else                     // else i * j now >= nmax
                break;               // break out of loop and try next i value
于 2013-10-03T18:31:22.113 に答える