$N$ 以下の素数の個数
ソースコード
nachia/math/counting-primes.hpp
主な機能
$N$ 以下の素数の個数を求める。
関数
CountingPrimes
long long CountingPrimes(long long maxval);
- $n = \text{maxval}$
- $0 \leq n \leq 10^{11}$
- $O(n^{3/4} / \log n)$ 時間
$n$ 以下の素数の個数を返す。
参考
えびちゃんの日記 | 眠れない夜は素数の個数でも数えましょう https://rsk0315.hatenablog.com/entry/2021/05/18/015511