生成从1到n的素数,崩溃n> 3亿

Question

有关如何让这个程序工作n = 1万亿(除了升级/购买新计算机)的任何建议？

错误如下:构建后,正在执行的程序(命令行样式输出窗口弹出)然后快速关闭,我得到以下错误"ProjectPrimes.exe已停止工作(Windows正在寻找解决方案这个问题."我怀疑这与内存问题有关,因为我第一次遇到n = 2000万,但那是在我选择malloc /释放'筛'阵列之前(即我的'筛'阵列是大阵列)尺寸nx 1,每个元素由1或0组成.

该程序需要大约35秒才能完成前3亿个整数(16,252,325个素数),所以没关系,但没什么了不起的.正如我所提到的,目标是能够产生低于1万亿的质数,所以我还有很长的路要走......

如果相关,这是我的机器规格(如果在这台机器上目标恰好是不合理的):2.40ghz i5,4GB RAM,64位Windows 7.

方法概述,对于那些不熟悉的人:我们使用Sienda of Sundaram方法.在没有进入证明的情况下,我们首先使用筛选函数消除整数"n"以下的所有奇数非素数:[2*(i + j + 2*i*j)+1 | i < - [1..n/2],j < - [i..an优化上限]].然后我们交掉偶数(当然不包括两个).这让我们留下了素数.

为什么prime函数返回(指向包含数组的指针)n下面的完整素数集？那么,目标是能够识别(i)n以下的素数以及(ii)列出n以下的素数.这也是为什么我选择传递一个指针,用于将n下面的素数计数作为参数.

这是不那么令人兴奋的"主要"功能:

int main() {
    long ceiling = 300*1000*1000;
    long *numPrimes;
    long *primes;

    primes = primesToSS(ceiling+1, numPrimes);
    printf("\n\nThere are %d primes below %d.\n\n",*numPrimes,ceiling);

    free(primes);
    return 0;
}

这是肉:

//n represents the ceiling, i.e., the integer below which we will generate primes
//cnt* is a pointer which will point the number of primes below n

long* primesToSS( long n, long* cnt ) {

    //initialize sieve by setting all elements equal to 1 (except for 0 and 1)
    long *sieve = malloc(n*sizeof(long));
    initArray(sieve, n, 1);
    sieve[0] = 0; sieve[1] = 0;

    //eliminate all odd composite numbers
    for (int i = 1; i <= n/2; ++i)
        for (int j = i; j <= (n-2*i)/(2*(2*i+1)); ++j)
            sieve[ 2*(i+j+2*i*j)+1 ] = 0;

    //eliminate all even numbers greater than two 
    //and count total number of primes below n
    long numPrimes = 1;
    for (int i = 3; i < n; ++i) {
        if (i % 2 == 0) sieve[i] = 0;
        numPrimes += sieve[i];
    }
    *cnt = numPrimes;

    //create array of primes
    long *primes = malloc(numPrimes*sizeof(int));
    long counter = 0;
    for (int i = 0; i < n; ++i) {
        if (sieve[i] == 1) {
            primes[counter] = i;
            counter++; } 
    }
    free(sieve);
    return primes;
}

void initArray( int* arr, int len, int n ) {
    for( int i = 0; i < len; ++i) arr[i] = n; }

Answer 1

让我们做一些观察:

• 正如人们在评论和答案中提到的那样,只需要1位来存储数字是否为素数.因此,您可以将8个数字的数据打包为1个字节.实现自己的bitset数据结构,使代码更清晰.
• 在评论中也提到,因为大于2的所有素数都是奇数,所以不需要存储偶数的数据.这允许您将16个数字打包成1个字节.
• 按照车轮分解的想法,你可以进一步将24个数字打包成1个字节,如果你只存储数字的位数为1或5模数6.更高的模数将节省更多的空间(收益递减),但逻辑为访问bitset数据结构可能会降低算法速度.
• 对于使用1万亿(10 ¹²)个数字的程序,正如您所筛选的那样,您只需要收集少于100万(10 ⁶)的素数列表.更大的数字是不必要的,因为列表中已经涵盖了化合物数量小于1万亿的其他因素.

• 打包数量为16个数字/字节(你应该做的最基本的设置),你需要~58 GiB的RAM.但是,没有必要为整个范围分配.只需分配几亿到几十亿的较小范围(尝试改变最高性能的数量),最多可以转化为几百MiB,然后使用不到100万的素数列表筛选范围.

  此步骤可以并行完成 - 您只需要共享少于100万的素数列表.

  顺便说一下,这种技术称为分段筛.