エラトステネスの篩とは？
エラトステネスの篩とは、一定範囲の素数を列挙する古典的アルゴリズム。2から順に、見つけた素数の倍数を配列上で消していき、消されずに残ったものを素数とする。1つずつ試し割りするより高速で、計算量はおよそ O(n log log n)。作業用の配列を確保するため、時間と空間のトレードオフを説明する題材として出題される。
えらとすてねすのふるい
エラトステネスの篩の意味
一定範囲の素数を列挙する古典的アルゴリズム。2から順に、見つけた素数の倍数を配列上で消していき、消されずに残ったものを素数とする。1つずつ試し割りするより高速で、計算量はおよそ O(n log log n)。作業用の配列を確保するため、時間と空間のトレードオフを説明する題材として出題される。
エラトステネスの篩の具体例
1〜100の素数を求めるなら、2の倍数、3の倍数、5の倍数、7の倍数を消せば足りる。10より大きい数から始める必要がないのは、100の平方根が10だから。合成数は必ず平方根以下の素因数を持つため、篩の外側ループは √n までで打ち切れる。
エラトステネスの篩は試験でどう引っ掛けられる？
各素数 p の倍数を消し始める位置を 2p ではなく p×p にできる点を見落とすと、無駄な走査が増える。また「篩は素数判定が速い」と誤解しやすいが、単一の数を判定するだけなら試し割りのほうが省メモリで有利。
エラトステネスの篩と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。