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