素数判定するよ

\(n\) 以下の素数の個数を求める関数 \(\pi(n)\) を持っていたとします。 このとき、\(n\) の素数判定は \(\pi(n)-\pi(n-1) = 1\) かどうかでできます。

fn is_prime(n: usize) -> bool {
    n > 0 && prime_pi(n) - prime_pi(n - 1) == 1
}

たとえば \(O(n^{3/4}/\log(n))\) でできます*1。

お粗末さまでした。

おまけ

素数の数え上げが気になる人向けの記事：

rsk0315.hatenablog.com

*1:素直に \(O(n^{1/2})\) 時間の試し割り法をしましょう。