algorithm - 打印出 N 以下所有素数的运行时间

Question

int main() {
      int i, a[N];
      // initialize the array
      for(i = 2; i < N; i++) a[i] = 1;
      for(i = 2; i < N; i++)
         if(a[i])
              for(int j = i; j*i < N; j++) a[i*j] =0;
       // pirnt the primes less then N
       for(i = 2; i < N; i++)
           if(a[i]) cout << "  " << i;
       cout << endl;
}

算法书中给出了我正在阅读的上述程序的运行时间与 N+N/2+N/3+N/5+N/7+N/11+... 成正比，

请帮助我理解作者是如何从程序中得出上述等式的。谢谢!文卡塔

Answer 1

这是寻找素数的“Eratosthenes 筛法”方法。对于每个素数，if(a[i])测试成功并执行内部循环。考虑这个内部循环如何在每一步终止(记住，条件是 j*i < N ，或者等价地， j < N/i ):

• i = 2 -> j = 2, 3, 4, ..., N/2
• i = 3 -> j = 3, 4, 5, ..., N/3
• i = 4 -> 不是素数
• i = 5 -> j = 5, 6, 7, ..., N/5
• ...

将操作总数(包括初始化数组/提取素数)相加得到书中提到的运行时间。

参见 this question有关更多信息，包括根据 Wikipedia article 讨论如何根据位运算将 O(n(log n)(log log n)) 扩展为 O(n(log n)(log log n)) .