N以下の素数の個数を求める Count Primes in LeetCode

問題

leetcode.com

解法

N√Nの解法だと間に合わない。

素数の倍数は全て素数ではないという性質を使って解く。 素数を見つけたら、その倍数を予め素数ではない印を付けておく。

ソースコード

参考

この解法の計算量はO(NloglogN)らしい。

www.youtube.com