找到 40 亿以下所有素数的最快方法

Question

我正在尝试打印 2**32 以下的每个素数。现在我正在使用布尔向量构建一个筛子，然后在制作筛子后打印出素数。仅打印 10 亿以内的素数就需要 4 分钟。有没有更快的方法来做到这一点？这是我的代码

#include <iostream>
#include <cstdlib>
#include <vector>
#include <math.h>

using namespace std;

int main(int argc, char **argv){
  long long limit = atoll(argv[1]);
  //cin >> limit;
  long long sqrtlimit = sqrt(limit);

  vector<bool> sieve(limit+1, false);

  for(long long n = 4; n <= limit; n += 2)
    sieve[n] = true;

  for(long long n=3; n <= sqrtlimit; n = n+2){
    if(!sieve[n]){
      for(long long m = n*n; m<=limit; m=m+(2*n))
        sieve[m] = true;
    }
  }

  long long last;
  for(long long i=limit; i >= 0; i--){
    if(sieve[i] == false){
      last = i;
      break;
    }
  }
  cout << last << endl;

  for(long long i=2;i<=limit;i++)
  {
    if(!sieve[i])
      if(i != last)
        cout<<i<<",";
      else
        cout<<i;
  }
  cout<<endl;

Answer 1

我在博客中讨论了生成大量素数的问题，其中我发现前十亿个素数的总和是 11138479445180240497。我描述了四种不同的方法：

1. 蛮力，使用试除法测试从 2 开始的每个数字。

2. 使用 2、3、5、7 轮生成候选项，然后使用对基数 2、7 和 61 的强伪素数测试来测试素数；这个方法最多只能计算 2^32，这不足以让我对前十亿个素数求和，但对你来说已经足够了。

3. Melissa O'Neill 提出的一种算法，使用嵌入优先级队列的筛子，速度相当慢。

4. 埃拉托色尼分段筛，速度非常快，但需要空间来存储筛分素数和筛子本身。