Pythonで素数を生成する方法をわかりやすく解説

素数とは何か？

素数とは、1とその数自身以外の正の整数では割り切れない数のことです。たとえば、2、3、5、7、11などが素数に該当します。なお、1は約数を1つしか持たないため、素数には含まれない点に注意しましょう。

Pythonで素数を判定する基本的な考え方

Pythonでは、剰余演算子「%」を使うことで、ある数が別の数で割り切れるかどうかを簡単に調べられます。x % y の結果が0であれば、xはyで割り切れることを意味します。

1から100までの範囲で素数を求める場合、各数値（仮にxとします）について、2からx-1までのすべての数で順番に割り切れるかを確認する必要があります。この処理は、二重ループ（ネストしたループ）によって実現できます。

サンプルコード

for x in range(2, 101):
    for y in range(2, x):
        if x % y == 0:
            break
    else:
        print(x, end=' ')

このコードを実行すると、1〜100の範囲にある素数が出力されます。ループの開始を2にしているのは、1が素数ではないためです。

実行結果

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

「for〜else」構文のポイント

上記のコードでは、Python特有の「for〜else」構文を活用しています。内側のループが break されずに最後まで完了した場合、つまり2からx-1までのどの数でも割り切れなかった場合にのみ、else ブロックが実行され、その数が素数として出力されます。これは他の多くの言語にはないPythonならではの書き方です。

より効率的な方法：平方根までチェックする

実は、xの約数はペアで存在するため、√x以下の数だけで割り切れるかを確認すれば十分です。これにより、無駄な計算を大幅に減らせます。

import math

for x in range(2, 101):
    is_prime = True
    for y in range(2, int(math.sqrt(x)) + 1):
        if x % y == 0:
            is_prime = False
            break
    if is_prime:
        print(x, end=' ')

大きな数を扱う場合は、こちらの方法の方がはるかに高速に動作します。さらに大規模な範囲の素数を求めたいときは、「エラトステネスのふるい」と呼ばれるアルゴリズムを検討するのもおすすめです。