エラトステネスのふるいとは？
エラトステネスのふるいとは、ある範囲の素数を列挙するアルゴリズム。2から順に、まだ消されていない数を素数として確定し、その倍数を全て消していく。1つずつ割り算で判定するより高速で、配列と二重の繰返しを使う典型例としてFEの擬似言語問題に登場する。
えらとすてねすのふるい
エラトステネスのふるいの意味
ある範囲の素数を列挙するアルゴリズム。2から順に、まだ消されていない数を素数として確定し、その倍数を全て消していく。1つずつ割り算で判定するより高速で、配列と二重の繰返しを使う典型例としてFEの擬似言語問題に登場する。
エラトステネスのふるいの具体例
1〜30なら、2を素数として4,6,8…を消し、次に残った3を素数として9,15,21…を消す。5、7と続け、残ったものが素数となる。倍数を消し始める位置をその数の2乗（3なら9）からにすると、既に消した分の重複を省ける。
エラトステネスのふるいは試験でどう引っ掛けられる？
消す処理を打ち切ってよいのは「調べる数が範囲の平方根を超えたとき」で、この判定条件が問われる。また1は素数ではないため最初から除外する。倍数を2倍から消すか2乗から消すかで処理回数が変わる。
エラトステネスのふるいと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。