pub fn prime_pi(n: usize) -> usizeExpand description
素数の数え上げ。
$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);