c++ - Sieve of Eratosthenes 算法的效率

Question

我正在尝试理解“Eratosthenes 筛法”。这是我的算法(下面的代码)，以及我无法理解的功能列表(按顺序)。

1. 为什么 i * i 比 i * 2 更有效？是的，我可以理解它会减少迭代次数，因此效率更高，但是它不会跳过一些数字(例如 i = 9 => j = 81 跳过 18 27 36 ...)?
2. 在维基百科上，我发现空间复杂度等于O(n)，这是可以理解的；无论我们输入什么数字，它都会创建一个输入大小的数组，但这里的时间复杂度会让事情变得困惑。我发现了这个符号 O(n(logn)(loglogn)) —— 那是什么？根据我的理解，我们有 2 次完整迭代和 1 次部分迭代，因此 O(n^2 * logn)。

#include <iostream>
using namespace std;

int main() {
  cout << "Enter number:" << endl;

  int arrSize;
  cin >> arrSize;

  bool primesArr[arrSize];
  primesArr[0] = false;
  for (int i = 1; i < arrSize; i++) primesArr[i] = true;

  for (int i = 2; i < arrSize; i++)

    if (primesArr[i - 1]) {
      cout << i << endl;
   /* for (int j = i * 2; j < arrSize; j += i) less efficient */
      for (int j = i * i; j < arrSize; j += i)
        primesArr[j - 1] = false;
    }

  return 0;
}

Answer 1

Why i * i more efficient than i * 2? Yes, I can understand it would be less iteration, therefore more efficiency, but then doesn't it skip some numbers (for example i = 9 => j = 81 skip 18 27 36 ...)?

你指的是

for (int j = i * i; j < arrSize; j += i)

请注意，i * i 是循环计数器 j 的初始值。所以j大于i * i的值都会被标记掉。我们从 i * 2 到 i * i 跳过的值在之前的迭代中已经被标记掉了。让我们想想前几个:

当 i == 2 时，我们标记出 2 的所有倍数(2、4、6、8 等)。当 i == 3 时，如果我们开始 j = 3 * 2 = 6 那么我们将在到达 9、12、15 等之前再次标记 6。因为 6 是2 的倍数并且已经被标记掉了，我们可以直接跳到 3 * 3 == 9。

当我们到达 i == 5 并且如果我们从 j == 5 * 2 == 10 开始，那么我们将标记 10，它已经被占用注意，因为它是 2 的倍数，15 是 3 的倍数，20 也是 2 的倍数，然后我们最终达到 25，这不是任何小于 5 的引物的倍数。

time complexity here is where things get confusing. I found this notation O(n(logn)(loglogn)) -- what is that? According to my understanding we have 2 full iterations and 1 partial iteration, therefore O(n^2 * logn).

您的分析得出正确的结果，该算法是 O(n^2 * logn)。 A more detailed analysis可以证明更严格的上限为 O(n(logn)(loglogn))。请注意，O(n(logn)(loglogn)) 是 O(n^2 * logn) 的子集。