0

我尝试了 Eratosthenes 的筛子：以下是我的代码：

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 万个素数。

一种方法可能是：

     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 回答