生成素数从1到n,崩溃对于n> 3亿 [英] Generate primes from 1 to n, crashing for n > 300 million

查看:235
本文介绍了生成素数从1到n,崩溃对于n> 3亿的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

任何建议,我怎么能(从制造升级/购买一台新的电脑除外)获得此程序为N = 1万亿工作?

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

该计划采取〜35来秒的第3亿整数(16252325素数)来运行这样也没关系,但没有壮观。正如我已经提到的,我们的目标是能够产生低于1万亿因此是一个长期的方式关闭...

素数

如果相关的,这里有我的机器规格的情况下(目标恰好是不合理的这台机器上):2.40GHz的i5处理器,4GB内存,64位的Windows 7

方法的概述,对于那些谁不熟悉:我们用孙达拉姆筛的方法。没有进入的证明,我们先消灭一个整数以下的所有奇非素数N用筛子功能:2 *(I + J + 2 * I * j)条+1 | I&下 - [1..n的/ 2],J&下 - [i..an优化上限]。然后,我们划掉偶数(排除两个,当然)。它留给我们的素数。

为什么黄金函数返回(一个指向包含数组)的整套下文的N素数?好,目标是要能够识别两个(ⅰ)的素数的数量低于n作为以及(ⅱ)在下面列出n中的素数。这也是为什么我选择了传球的指针为下文的N素数的计数作为参数。<​​/ P>

这里是不那么令人兴奋的'主'的功能:

  INT的main(){
    长的顶棚= 300 * 1000 * 1000;
    长* numPrimes;
    长*素数;    素数= primesToSS(上限+ 1,numPrimes);
    的printf(\\ n \\ n有低于%D的素数\\ n \\ n,* numPrimes,吊顶);    免费(素数);
    返回0;
}

和这里的肉:

  // N RE presents天花板上,即,整数下面我们将生成的素数
// CNT *是一个指针,指向下文的N素数数长* primesToSS(N久,长* CNT){    //通过设置等于1的所有元素初始化筛(除0和1)
    长*筛=的malloc(N * sizeof的(长));
    initArray(筛中,n,1);
    筛[0] = 0;筛[1] = 0;    //消除所有奇数合数
    的for(int i = 1; I&LT; = N / 2; ++ I)
        为(中间体J =; J&下; =(N-2 *ⅰ)/(2 *(2 * i + 1的)); ++ j)条
            筛[2 *(I + J + 2 * I * j)条+1] = 0;    //消除所有偶数大于二
    //和计数下文的N素数的总数
    长numPrimes = 1;
    的for(int i = 3; I&LT; N ++我){
        如果(ⅰ%2 == 0)筛[I] = 0;
        numPrimes + =筛[I]
    }
    * CNT = numPrimes;    //创建素数数组
    长*素数=的malloc(numPrimes *的sizeof(INT));
    柜长= 0;
    的for(int i = 0; I&LT; N ++我){
        如果(筛由[i] == 1){
            素数[计数器] =我;
            反++; }
    }
    免费(筛);
    返回素数;
}无效initArray为(int *改编,INT LEN,INT N){
    的for(int i = 0; I&LT; LEN ++我)常用3 [I] = N; }


解决方案

让我们做一些意见:


  • 随着人们评价和答案都提到,你只需要1位存储号码是否是一个素数。因此,你可以收拾8号数据到1个字节。实现自己的位集的数据结构,使code清洁。

  • 另外,在评论中提到,由于所有素数大于2是奇数,就没有必要存储数据为偶数。这允许你收拾16号到1个字节。

  • 轮分解的想法,可以进一步打包24号到1个字节,如果你只存储为全等要求1或5的模6.高等模数位将节省略微更多的空间(具有递减返回),但访问位集数据结构中的逻辑可以在算法慢下来。

  • 有关程序与工作1万亿(10 12 )的数字,因为你筛,你只需要收集素数不到100万(10 6 )。较大的数字是不必要的,因为在化合物号码其他因子小于1万亿将已经被覆盖的列表。

  • 在16号/字节(你应该做的最基本的设置)

    包装号码,您将需要〜58吉布的RAM。然而,没有必要分配给的整个范围。只是分配为更小的范围内几百亿至数十亿号码(尝试以改变对于最高性能的数量),其转化为至多几百MIB,然后用素数的列表中不到1万至筛范围。

    这一步可以并行完成 - 你只需要分享素数不到100万的名单

    顺便说一句,这种技术被称为分段筛。


Any suggestions as to how I can get this program to work for n = 1 trillion (aside from making upgrades / buying a new computer)?

The error is as follows: after building, the program being executing (the command line style output window pops up) and then quickly closes out, and I get the following error "ProjectPrimes.exe has stopped working (Windows is looking for a solution to this problem." I suspect this has to do with memory issues as I first encountered it at n = 20 million but that was before I chose to malloc/free the 'sieve' array (i.e., my 'sieve' array is the big array of dimensions n x 1 and with each element consisting of a 1 or 0).

The program takes ~35 seconds to run through the first 300 million integers (16,252,325 primes) so it's okay but nothing spectacular. As I'd mentioned, the goal is to be able to generate primes below 1 trillion so am a long ways off...

If relevant, here are my machine specs (in case the goal happens to be unreasonable on this machine): 2.40ghz i5, 4gb RAM, 64bit Windows 7.

An overview of methodology, for those who aren't familiar: we use the Sieve of Sundaram approach. Without getting into the proof, we first eliminate all odd non-primes below an integer "n" using the sieve function: [2*(i+j+2*i*j)+1 | i <- [1..n/2], j <- [i..an optimized upper bound]]. We then cross off the even numbers (excluding two, of course). Which leaves us with the primes.

Why does the prime function return (a pointer to an array containing) the complete set of primes below n? Well, the goal is to be able to identify both (i) the number of primes below n as well as (ii) list the primes below n. This is also why I chose to pass a pointer for the count of primes below n as an argument.

Here's the not-so-exciting 'main' function:

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;
}

And here's the meat:

//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; }

解决方案

Let's make some observations:

  • As people have mentioned in the comments and answers, you only need 1 bit to store whether a number is a prime. Therefore, you can pack the data for 8 numbers into 1 byte. Implement your own bitset data structure to make the code cleaner.
  • Also mentioned in the comments, since all prime numbers larger than 2 are odd numbers, there is no need to store data for even numbers. This allow you to pack 16 numbers into 1 byte.
  • Following the idea of wheel factorization, you can further pack 24 numbers into 1 bytes, if you store only the bits for numbers congruent to 1 or 5 modulo 6. Higher modulo will save slightly more space (with diminishing return), but the logic to access the bitset data structure may slow down the algorithm.
  • For the program to work with 1 trillion (1012) numbers, as you sieve, you only need to collect the list of prime numbers less than 1 million (106). Larger numbers are unnecessary, since the other factor in the compound numbers less than 1 trillion would already have been covered by the list.
  • Packing numbers at 16 numbers/byte (the most basic setup you should do), you would require ~58 GiB of RAM. However, there is no need to allocate for the whole range. Just allocate for a smaller range of a few hundred million to a few billion numbers (try to vary the number for highest performance), which translate to at most a few hundred MiB, then use the list of prime number less than 1 million to sieve the ranges.

    This step can be done in parallel - you only need to share the list of prime numbers less than 1 million.

    By the way, this technique is called segmented sieve.

这篇关于生成素数从1到n,崩溃对于n&GT; 3亿的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆