運行時間打印出下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的篩。此圖片說明了一切：

（維基百科）