运行时间打印出下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+...，

请帮助我理解作者是如何想出了上面的方程来自程序。 谢谢！ Venkata

Answer 1

这是寻找素数 “的埃拉托色尼筛” 的方法。对于每个素数，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
• ...

求和的总NUM操作（包括初始化数组/提取素数）给出了本书中提到的运行时。

请参阅this question以获取更多信息，包括讨论如何根据位操作将这变为O（n（log n）（log log n））的扩展，如Wikipedia article。

Answer 2

仅针对素数i s执行内部循环（在if(a[i])之内）。即，对于i等于2,3,5,7,11，...并且对于单个i，该循环具有大约N/i迭代。因此，我们总共有N/2 + N/3 + N/5 + N/7 + N/11 + ...次迭代。

Answer 3

该算法被称为Eratosthenes的筛。此图片说明了一切：

（维基百科）