rsk0315 https://blog.hatena.ne.jp/rsk0315/ えびちゃんの日記 https://rsk0315.hatenablog.com/ 別に、おふとんから出たくない朝とかに数えてもいいと思います。 \(n\) 以下の素数の個数を数えたいときどうしますか？ 各整数 \(2\le i\le n\) に対して素数判定して数えます？ 素数判定を試し割り法でやると \(\Theta(n\sqrt{n})\)、線形篩*1を使えば \(\Theta(n)\) とかですね。 これを \(o(n)\) でできたらうれしくないですか？という話です。 今回は \(O(\sqrt{n})\) space, \(O(n^{3/4}/\log(n))\) time の話がメインです。 定数倍があまり軽くない \(O(n^{2/3})\) space, \… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Frsk0315.hatenablog.com%2Fentry%2F2021%2F05%2F18%2F015511" title="眠れない夜は素数の個数でも数えましょう - えびちゃんの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-05-18 01:55:11 rich https://rsk0315.hatenablog.com/entry/2021/05/18/015511 1.0 100%