エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
線形篩で遊ぼう - えびちゃんの日記
線形篩と呼ばれているアルゴリズム・データ構造があります。 「線形時間で前計算できる何々」を「線形何... 線形篩と呼ばれているアルゴリズム・データ構造があります。 「線形時間で前計算できる何々」を「線形何々」と呼ぶのは不適切ですか、もしかして?*1 ざっくり紹介 構築に関して 発展編 実装 練習問題 おわり $\gdef\lpf{\operatorname{lpf}}$ ざっくり紹介 線形篩の構築は、各 $i$ ($2\le i\le n$) に対して 最小素因数 (least prime factor) $\lpf(i)$ を求めるものであり、これを $O(n)$ 時間で行います。 これにより、$i$ の素数判定を $\lpf(i) = i$ でできるわけです。 また、構築の過程で $n$ 以下の素数の列挙も行うので、素数の列挙をしたいときにはそのまま使うこともできます。 構築に関して 下記の考察に基づきます。 整数 $i\ge 2$ に対して、$j\le\lpf(i)$ なる各素数 $j$