关于 Eratosthenes 埃氏筛法的时间复杂度
这货居然是 \(O(n\ln\ln n)\) 的！！！（我一直以为是 \(O(n\ln n)\)）
证明
就是说已经很接近线性了 qwq。
| \(n\) | \(\ln\ln n\) |
|---|---|
| \(10^4\) | \(2.2\) |
| \(10^5\) | \(2.4\) |
| \(10^6\) | \(2.6\) |
| \(10^7\) | \(2.8\) |
| \(10^8\) | \(2.9\) |
| \(10^9\) | \(3.0\) |
| \(10^{18}\) | \(3.7\) |
| \(10^{100}\) | \(5.4\) |