指定した範囲内のすべての素数を出力するPythonプログラム

この記事では、以下の問題文に対する解決方法について学んでいきます。

問題文

ある区間が与えられたとき、その範囲内に含まれるすべての素数を求めて出力する必要があります。

ここでは、素数の基本的な定義に基づいた全探索（ブルートフォース）によるアプローチを紹介します。素数とは、「1とその数自身のみを約数として持ち、それ以外の数を約数に持たない自然数」のことです。

この定義に基づき、各数値が素数の条件を満たしているかどうかを判定し、条件が真（True）と評価されるたびに出力処理を行います。

それでは、実際の実装例を見ていきましょう。

実装例

start = 1
end = 37
for val in range(start, end + 1):
    # valが2からval-1までのいずれかの数で
    # 割り切れる場合、それは素数ではない
    if val > 1:
        for n in range(2, val):
            if (val % n) == 0:
                break
        else:
            print(val)

出力結果

2
3
5
7
11
13
17
19
23
29
31
37

コードの解説

このプログラムの動作を順番に見ていきます。

• range(start, end + 1)：startからendまでのすべての整数を順に取り出します。end + 1としているのは、range関数の終端が排他的（end自体を含まない）であるためです。
• if val > 1：1は素数ではないため、1より大きい数値のみを判定対象とします。
• for n in range(2, val)：2からval-1までのすべての数で割り切れるかどうかを確認します。
• break：途中で割り切れる数が見つかった時点で、その数は素数ではないためループを抜けます。
• else節：forループがbreakされずに最後まで完了した場合（＝どの数でも割り切れなかった場合）のみprint(val)が実行されます。これはPython特有の「for-else」構文です。

なお、上記のコードで使用されている変数はすべてローカルスコープ内で宣言されており、それぞれの参照関係は図のようになっています。

計算量について

この方法はシンプルで理解しやすい反面、計算量はO(n²)となり、大きな範囲を扱う場合は非効率になります。より高速に素数を列挙したい場合は、エラトステネスのふるいなどのアルゴリズムを使用することをおすすめします。

まとめ

この記事では、指定した区間内のすべての素数を出力する方法について学びました。素数の定義に基づくシンプルな全探索のアプローチは、プログラミングの基礎を理解するのに非常に適した題材です。ぜひ自分でもコードを書いて、動作を確認してみてください。