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

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

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

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

如果相关，这是我的机器规格（如果在这台机器上目标恰好是不合理的）：2.40ghz i5,4GB RAM，64位Windows 7。

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

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

这是不那么令人兴奋的“主要”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; } 

这是肉：

 //n represents the ceiling, ie, 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万的素数列表。

  顺便说一下，这种技术称为分段筛。

Answer 2

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

正如Blastfurnace所指出的那样，你正在取消引用（和存储）一个未初始化的指针。 这应该是

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

可能还有其他错误……特别是没有检查malloc失败。 哦，这是一个：

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

int和long是不同的类型。 在这里你再次这样做：

 long *primes = malloc(numPrimes*sizeof(int)); 

最佳做法是使用sizeof元素而不是类型，这可以避免这种情况：

 long *primes = malloc(numPrimes * sizeof *primes); 

检查代码是否存在其他明显错误。

样式注释：将}放在一行的末尾是不好的做法，并在以后添加另一行时请求错误。

Answer 3

一些内存注意事项：对于前1万亿个素数，如果用一个比特代表每个数字，则需要1万亿/ 8个字节。 那是125000000000 = 119209 MB = 116 GB的RAM。

虽然您可以要求您的操作系统创建一个200GB的SWAP分区，但性能可能会很差。 如果要保持相同的算法，则需要查看内存映射文件 。

那仍然会很慢，但至少你可以分配一个足够大的数组。

接下来的步骤将是查看不同的主要算法，或者您需要研究内存压缩算法。 在您的情况下， 稀疏矩阵将无法正常工作，因为您的起始矩阵全部为1，并且您最终删除了几乎所有元素。