Pythonで指定した範囲内のすべての素数を出力する方法

素数とは何か

素数とは、1とその数自身以外の正の整数では割り切れない数のことです。たとえば、2、3、5、7、11などが素数に該当します。ある数が素数かどうかを判定するには、その数自身と1を除く、1からその数までの間にあるすべての整数で割り切れるかどうかを確認する必要があります。

Pythonで範囲内の素数を求める基本的な考え方

以下のプログラムは、1から100までの間にあるすべての素数を出力します。仕組みは次のとおりです。

• 外側のループで、判定対象となる範囲内の各数値を順番に生成します。
• 内側のループで、2からその数値の手前までの整数を使い、剰余演算子「%」で割り切れるかどうかを順にチェックします。
• 一度でも割り切れた場合は素数ではないため、break文で内側のループを抜けます。
• 最後まで割り切れなかった場合のみ、その数は素数として出力されます。

サンプルコード

for i in range(101):
    for j in range(2, i - 1):
        if i % j == 0:
            break
    else:
        print(i)

コードのポイント

このプログラムで重要なのが、Python特有の「for-else」構文です。elseブロックは、内側のループがbreakされずに最後まで完了したときにだけ実行されます。つまり、「どの数でも割り切れなかった＝素数である」という条件を簡潔に表現できます。

なお、range(2, i - 1)としているため、i自体と1による割り算は自動的に除外されます。また、range(101)は0から100までを生成しますが、0と1は素数の定義上該当しないため、実際に出力されるのは2以降の素数です。

実行結果（出力例）

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

より効率的な方法

大きな範囲の素数を求めたい場合は、平方根まで調べる方法や、エラトステネスのふるいと呼ばれるアルゴリズムを使うと処理速度を大幅に改善できます。特に広い範囲を扱う場合は、エラトステネスのふるいが定番のアプローチです。