Function nekolib::math::prime_pi_::prime_pi

source ·
pub fn prime_pi(n: usize) -> usize
Expand 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);

References

See also