给定范围的埃拉托色尼筛法

Question

我试图在 C++ 中生成从 N 到 N_Max 的素数序列。我的方法是使用埃拉托色尼筛法生成这些素数：

void runEratosthenesSieve(int upperBound) {
      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
      for (int m = 2; m <= upperBoundSquareRoot; m++) {
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";
      delete [] isComposite;
}

但是这个函数计算素数 1 到 N 会浪费内存。有没有一个函数可以运行更快并且占用更少的内存？

Answer 1

您需要做的就是确定 sqrt(N_max) 以内的值是质数还是合数 - 正如您已经在做的那样。然后从 N 循环到 N_max 并确定每个值是否可以被找到的素数整除（在 2 和 sqrt(N_max) 之间）。

这只是对您的方法的一个小调整。

旁白：不是使用浮点数来计算平方根（即 sqrt()），而是使用简单的算法来计算 "integer square root"（即给定一个值 M，找到值 R，它是满足 R*R <= M 的最大整数）。使用您最喜欢的搜索引擎轻松找到。优点是它让你远离浮点的细微差别，而不必转换回整数。

给定范围的埃拉托色尼筛法

Sieve of Eratosthenes Given with Range

c++

primes

sieve-of-eratosthenes