0

私はエラトステネスのふるいを試しました：以下は私のコードです：

void prime_eratos(int N) {
    int root = (int)sqrt((double)N);
    bool *A = new bool[N + 1];
    memset(A, 0, sizeof(bool) * (N + 1));
    for (int m = 2; m <= root; m++) {
        if (!A[m]) {
            printf("%d  ",m);
            for (int k = m * m; k <= N; k += m)
                A[k] = true;
        }
    }

    for (int m = root; m <= N; m++)
        if (!A[m])
            printf("%d  ",m);
    delete [] A; 
}

int main(){

    prime_eratos(179426549);
    return 0;
}

時間がかかりました：私のシステムでは実際の7.340秒です。

私はまた、アトキンのふるいを試しました（エラトステネスのふるいよりも速くどこかで勉強しました）。

しかし、私の場合は時間がかかりました：実際の10.433秒。

コードは次のとおりです。

int main(){
    int limit=179426549;
    int x,y,i,n,k,m;
    bool *is_prime = new bool[179426550];

    memset(is_prime, 0, sizeof(bool) * 179426550);

    /*for(i=5;i<=limit;i++){
      is_prime[i]=false;
      }*/
    int N=sqrt(limit);
    for(x=1;x<=N;x++){
        for(y=1;y<=N;y++){
            n=(4*x*x) + (y*y);
            if((n<=limit) &&(n%12 == 1 || n%12==5))
                is_prime[n]^=true;
            n=(3*x*x) + (y*y);
            if((n<=limit) && (n%12 == 7))
                is_prime[n]^=true;
            n=(3*x*x) - (y*y);
            if((x>y) && (n<=limit) && (n%12 == 11))
                is_prime[n]^=true;
        }
    }
    for(n=5;n<=N;n++){
        if(is_prime[n]){
            m=n*n;
            for(k=m;k<=limit;k+=m)
                is_prime[k]=false;

        }
    }
    printf("2   3   ");
    for(n=5;n<=limit;n++){
        if(is_prime[n])
            printf("%d   ",n);
    }
    delete []is_prime;
    return 0;
}

さて、1秒間に100万個の素数を出力できるものはないのだろうか。

1つのアプローチは次のとおりです。

     I store the values in Array but the program size is limited.

誰かが私に最初の100万の素数をより少なくする方法を提案してもらえますか

制約を満たす秒よりも（上記で説明）？

ありがとう!!

4

4 に答える 4

4

試す

int main()
{
    std::ifstream  primes("Filecontaining1MillionPrimes.txt");
    std::cout << primes.rdbuf();
}
于 2012-06-14T20:03:49.280 に答える
2

素数を間違って数えました。百万番目の素数は15485863であり、これはあなたが提案するよりもはるかに小さいです。

ふるいから偶数を削除することで、プログラムを高速化し、スペースを節約できます。

于 2012-06-14T19:57:00.937 に答える
0

数値が素数であるかどうかを確認する最も速い方法は、複合性を確認することです。http：//en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_testを実装し、RSAで大成功を収めました。確率的で、実行回数に応じて高い成功率を示します。

于 2012-06-14T20:03:39.317 に答える
-1

ステップ1.printfを実行しないでください

ステップ2.より高速なコンピューターを購入します。

于 2012-06-14T19:50:59.343 に答える