问题描述
任何建议，我怎么能（从制造升级/购买一台新的电脑除外）获得此程序为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素数的计数作为参数。
这里是不那么令人兴奋的'主'的功能：
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 ）的数字，因为你筛，你只需要收集素数不到100万（10 ) numbers, as you sieve, you only need to collect the list of prime numbers less than 1 million (10). 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亿的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！