将Eratosthenes筛网扩展到十亿以上

void sieve_of_eratosthenes(){
    bool* a;
    a = (bool*)malloc(MAX * sizeof(bool));
    memset(a, true, MAX);
    unsigned long int i = 1;
    while (i < MAX){

        while (((++i)<MAX)&&(!a[i]));

        if (2 * i >= MAX)
            break;

        for (unsigned long int k = 2 * i; k < MAX; k += i)
            if (a[k])
                a[k] = false;
    }
    std::cout << "done\n";
    for (unsigned long int i = 2; i < MAX; i++)
        if (a[i])
            std::cout << i << "\n";
    getchar(); getchar();
}

#1 楼

有很多方法可以使运行速度更快。

首先，通过仅将奇数存储在筛子中来节省大量空间。唯一的偶数是2。请注意，在现代计算机上，算法花费的时间大致等于其读取和写入的数据量，因此将所需空间减半将使执行时间减半。因此索引\ $ i \ $的布尔值表示数字\ $ 2_i + 1 \ $。

现在您只需要删除奇数即可。最初将所有内容都设置为true时，因为1不是素数，所以将array[0]设置为false。现在，当您删除素数p的倍数时，您会知道所有小于\ $ p ^ 2 \ $的倍数都已被删除，因此您开始在\ $ p ^ 2 \ $处删除素数的循环。并且您一次增加2p，因为p*p，(p+2)*p和(p+4)*p等是p的奇数倍。并且由于删除的第一个素数是\ $ p ^ 2 \ $，因此当\ $ p ^ 2 \ $ <= MAX时，可以停止循环查找素数。

现在情况有些棘手：您正在寻找下一个质数p。为此，您检查一个[i]，直到找到一个正确的。索引i映射到素数p = 2i + 1。 \ $ p ^ 2 \ $是一个奇数，数字\ $ p ^ 2 \ $存储在索引j = (p^2 - 1) / 2。因此，请清除数字[j]，[j + p]等。

到目前为止，这很简单，现在我们变得更聪明了。您的MAX很大，例如\ $ 10 ^ 9 \ $。当您删除3的倍数时，您将得到一个重复的模式。对于p = 1、3、5、7、9、11、13、15、17的数字，您将获得模式（true，false，true），（true，false，true），（true，false，true）等等。三个值永远重复。用该模式填充前15个数字，然后删除5的倍数：删除后从（T，F，T，T，F，T，T，F，T，T，F，T，T，F，T）您保留的5的倍数（T，F，F，T，F，T，T，F，T，T，F，T，F，F，T）。十五个布尔型的这种模式将永远重复。您制作了7个副本，给出了105个数字，并删除了7的倍数。您制作了11个副本，给出了1155个数字，并删除了11的倍数。您制作了13个副本，给出了15,015个数字，并删除了13的倍数。您可能制作了17个副本，给出了255,255个数字。并删除17的倍数。这非常快，因为您没有十亿个数字，只有几十万个数字。完成后，使用memcpy将数据复制到整个数组中。对于最后一部分，您需要注意不要覆盖数组的末尾。那只是六个数字，但是这六个数字在工作中起着非常重要的作用！

对于其他质数，您将删除所有奇数倍数。我们可以更快地做到这一点。取p =101。将删除101p，103p，105p，107p等。但是105p可被3整除，因此已被删除。同样适用于111p，依此类推。因此，您可以执行以下操作：删除\ $ p ^ 2 \ $。如果p+2不能被3整除，则还要删除(p+2)*p。您要删除的下一个数字将是3的倍数。因此，您不必将每次删除的数字增加2p，而是增加4p（避免使用3的倍数），然后增加2p，然后再增加4p，2p ，4p，2p等。这样可以节省三分之一的工作。

另一项改进：您只使用一位，而不用一个字节来存储每个数字。这意味着您需要执行移位操作才能访问每个位，但是使用的内存量减少了1倍。这使您可以处理更大的数字，而更少的内存将更快地工作。

最后一个大问题：优化内存访问。假设您有MAX = 10亿，并且每个奇数= 62.5兆字节使用一位。这远远超过了您的处理器缓存。假设您有2MB的L3缓存= 3200万个数字。在这种情况下，您将对前3200万个数字完全执行筛选操作。因为您的数据全部在L3缓存中，所以运行速度会更快。假设您有256KB二级缓存= 400万个数字。在这种情况下，您将对前400万个数字完全执行筛选操作，然后对接下来的400万个数字执行筛选操作，依此类推。这甚至更快，因为现在您使用的所有数据都在二级缓存中，并且可以非常快速地读取/写入。

#2 楼

您可以做一些事情：


使用位向量（带有位操作）代替布尔数组。这样可以为您提供8倍的内存。如果使用C ++ vector< bool>，则可以免费获得此优化。
在数组中仅存储奇数。这将在内存中节省2的额外系数。您需要稍微调整程序的逻辑，但这并不是非常困难。这也节省了一些时间，因为在第一次迭代中，算法仅标记了一半的数字。
外循环（while (i < MAX)）只需从0到ceil(sqrt(MAX))即可运行。
内循环可以从i*i开始不只是2*i。

总结前两个将为您提供16倍的内存（或给定内存可筛选的16个数字），而后两个将显着提高运行时间（不请确定精确到多少。）段错误很可能是由于a == NULL（即malloc例程无法分配内存）这一事实造成的。您需要在NULL调用之后和malloc之前检查memset。

#3 楼

尽管最好在C ++中使用容器类，而不是手动分配内存，但我仍要指出这一点，因为仍然应该这样说：

a = (bool*)malloc(MAX * sizeof(bool));

在C ++中，最好使用new而不是malloc()。这也将避免需要这种强制转换，而C ++不需要这种强制转换。

您还可以初始化a，而不是先声明然后分配给它。

bool* a = new bool[MAX];

但是您仍然应该使用容器类，如@Andreas H所述。此外，您从未在这里使用free()，因此此函数将导致内存泄漏。

#4 楼

您是否有某些原因需要使用筛子？我还没有尝试使用建议的压缩方法来减少内存使用，但是简单测试直到平方根路由的所有内容，都会使您正在使用的Sieve的实现不可行。一旦开始导致缓存丢失，就无法筛分Sieve的性能，即使使用位打包，也无法将其保留在L1缓存中。