Function nekolib::math::prime_pi_::prime_pi

pub fn prime_pi(n: usize) -> usize

素数の数え上げ。

$n$ 以下の素数の個数 $\pi(n)$ を返す。

Complexity

$O(\sqrt{n})$ space, $O(n^{2/3} / \log(n)^{1/3})$ time.

Examples

use nekolib::math::prime_pi;

assert_eq!(prime_pi(10), 4);
assert_eq!(prime_pi(100), 25);
assert_eq!(prime_pi(1000), 168);
assert_eq!(prime_pi(10000), 1229);
assert_eq!(prime_pi(100_000_000_000), 4118054813);

References

• https://rsk0315.github.io/slides/prime-counting.pdf

See also

• https://rsk0315.hatenablog.com/entry/2021/05/18/015511
• https://judge.yosupo.jp/submission/7976
• https://math314.hateblo.jp/entry/2016/06/05/004332
• https://projecteuler.net/thread=10;page=5#111677