素数カウント( $\mathrm{O}(N^{\frac{2}{3}})$ )
(multiplicative-function/prime-counting-o2d3.hpp)
Min_25氏の記事およびツイートを参考にした素数カウントの$\mathrm{O}(N^{\frac{2}{3}})$での実装。実装の詳細はコメントに記した。
計算量は改善されているが、競プロの制約($N \leq 10^{11}$)ではシンプルな実装と実行速度に大きな差が出ないようだ。
TODO: 計算量解析を書く
Depends on
Verified with
Code
Back to top page