別に、おふとんから出たくない朝とかに数えてもいいと思います。 \(n\) 以下の素数の個数を数えたいときどうしますか？ 各整数 \(2\le i\le n\) に対して素数判定して数えます？ 素数判定を試し割り法でやると \(\Theta(n\sqrt{n})\)、線形篩*1を使えば \(\T…