ループで素数を列挙する
ループで素数を列挙する とは
for と while を組み合わせて、n 以下の素数を昇順に並べたリストを返すアルゴリズムを実装する。
ループで素数を列挙する
ループの応用編として、素数 (prime number) の列挙にチャレンジします。素数とは「1 と自分自身以外で割り切れない、2 以上の整数」のことです。2, 3, 5, 7, 11, 13, ... と続きます。本レッスンでは、整数 n を受け取り、n 以下の素数を昇順に並べたリストを返す関数を、入れ子ループで実装します。
素数判定は古典的なアルゴリズム題材で、ループの理解度を試す良いトレーニングです。
素数判定の方針
判定の最も基本的な形は、「2 から 候補値 - 1 まで全部試して、どれでも割り切れなければ素数」というものです。さらに賢くする方法もありますが、まずはシンプルに書きましょう。
n < 2のとき、その数は素数ではないn == 2のとき、最小の素数として認める- それ以外は
i = 2, 3, ..., n - 1を試し、1 つでも割り切れたら素数ではない
Python
def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return Truen % i == 0 は「n が i で割り切れる」という意味です。割り切れる i が見つかった瞬間に return False で関数を抜け、見つからずループを抜けたら return True で素数だと判定します。
for ループの外で True を返す形は、線形探索 + 否定 のお決まりパターンです。
列挙する関数の組み立て
素数判定ができれば、2..n を回しながら判定を呼ぶだけで、素数のリストが手に入ります。
Python
def list_primes(n):
result = []
for candidate in range(2, n + 1):
is_prime = True
for i in range(2, candidate):
if candidate % i == 0:
is_prime = False
break
if is_prime:
result.append(candidate)
return result外側のループで判定したい candidate を 1 つずつ取り出し、内側のループで 2..candidate - 1 を試します。割り切れる数があれば break で早期離脱し、is_prime フラグを False にします。最後にフラグが True のままなら、result に追加します。
breakは内側のループだけ抜けます。外側はそのまま動き続けます。
動きを追ってみる
n = 10 のときの流れを簡略化したフローで示します。
n = 10 のとき、判定対象は 2, 3, 4, ..., 10。素数と判定されるのは 2, 3, 5, 7 で、結果は [2, 3, 5, 7] です。
よくある間違い
素数の列挙でつまずきやすいポイントは次の通りです。
n以下なのにrange(2, n)と書いてn自身を判定し忘れるis_prime = Trueの初期化を内側ループ前ではなく 外 に置く- 内側ループで
breakし忘れて、最後まで全部試して遅くなる n % i == 0をn / i == 0と書き間違えるn < 2のチェックを忘れて、0や1を素数として返す
Python
# NG: フラグの初期化を外側ループの外に置いてしまった
is_prime = True
for candidate in range(2, n + 1):
for i in range(2, candidate):
if candidate % i == 0:
is_prime = False
break
if is_prime:
result.append(candidate)このコードでは、is_prime が一度 False になると 二度と True に戻らない ので、2 以外の全部の数が「合成数」と判定されてしまいます。フラグは判定する数ごとに初期化するのが鉄則です。is_prime = True の位置を必ず内側ループの 前 に置きましょう。
入れ子ループでフラグを使うときは、「どの繰り返しごとに初期化するか」を強く意識します。
やってみよう
このレッスンでは、整数 n を受け取り、n 以下の素数を昇順に並べたリストを返す関数 list_primes(n) を実装します。n が 1 以下のときは空リストを返してください。n = 10 のときの結果は [2, 3, 5, 7]、n = 20 のときは [2, 3, 5, 7, 11, 13, 17, 19] です。外側のループで候補を回し、内側のループで割り切れる数を探す、という典型的な入れ子の使い方を体に染み込ませましょう。
余裕があれば、内側ループの上限を
int(candidate ** 0.5) + 1にすると高速化できることも確認してみましょう。
よくある質問
Q. このトピックは Python 以外の言語でも同じ書き方ですか？
A. 考え方は他言語と共通ですが、構文や標準ライブラリは異なります。Python はインデントでブロックを表し、コロン + 改行で構造を作るのが特徴です。他言語に移行する際は基本概念を維持しつつ、構文の差分を意識して書き換えると混乱が少ないです。
Q. 実行してエラーが出た場合の対処は？
A. エラーメッセージの最後の行（TypeError や NameError などの型）から原因と該当行を確認します。Python はトレースバックが下から上に読むと「呼び出し元 → 内部」の順で辿れます。print や IDE のデバッガで途中の変数を確認すると原因が見えてきます。
Q. 次のステップで何を学ぶべきですか？
A. 本レッスンの内容を理解できたら、本文の「やってみよう」を実装し、章末クイズに進むのがおすすめです。さらに自分のミニアプリ（電卓・todo・スコア集計など）に応用するとスキルが定着します。詰まったら本文の H2 セクションに戻って読み返してください。
次のレッスン
次は 第 5 章クイズ ループ で、for と while を組み合わせて、n 以下の素数を昇順に並べたリストを返すアルゴリズムを実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 素数判定 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 素数判定 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 外側の for で 2..n を回すこと
- 内側の for で割り切れる数を探すこと
- 戻り値は素数を昇順に並べたリストにすること
入出力例
test-cases.txt
list_primes(10) → [2,3,5,7]
list_primes(1) → []
list_primes(2) → [2]
list_primes(20) → [2,3,5,7,11,13,17,19]
list_primes(0) → []