Pythonで素数を見つける3つの方法を徹底解説【初心者向け】

はじめに：素数とは？

まず、素数とは何かを確認しておきましょう。

素数とは、1とその数自身という、ちょうど2つの整数でしか割り切れない正の整数のことです。なお、1は素数には含まれません。代表的な素数としては、2、3、5、7、11などが挙げられます。

この記事では、Pythonを使って素数を見つけるための3つの方法を、サンプルコードと実行結果とともに段階的に解説していきます。それぞれの方法で処理速度や効率がどう変わるのかにも注目しながら読み進めてください。

方法1：シンプルなforループを使う

最も基本的なのは、ネストしたforループ（二重ループ）を使う方法です。外側のループで2から指定した数値未満までの各候補を取り出し、内側のループで「その数が他の数で割り切れるか」をすべて調べます。

サンプルコード

def primemethod1(number):
    # 結果を格納するリストを初期化
    my_primes = []
    for pr in range(2, number):
        isPrime = True
        for i in range(2, pr):
            if pr % i == 0:
                isPrime = False
        if isPrime:
            my_primes.append(pr)
    print(my_primes)

primemethod1(50)

出力結果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

この方法はロジックが直感的で理解しやすい反面、割り切れることが確定しても内側のループが最後まで回り続けてしまうため、扱う数値が大きくなると処理効率が大きく低下します。

方法2：break文を組み合わせて無駄をなくす

次の方法では、break文を追加します。ある数で割り切れた時点で「その数は素数ではない」と判断できるため、それ以上の計算を打ち切り、無駄な繰り返しを省きます。

サンプルコード

def primemethod2(number):
    # 結果を格納するリストを初期化
    my_primes = []
    for pr in range(2, number + 1):
        isPrime = True
        for num in range(2, pr):
            if pr % num == 0:
                isPrime = False
                break
        if isPrime:
            my_primes.append(pr)
    return my_primes

print(primemethod2(50))

出力結果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

方法1との主な違いは以下の2点です。

• 割り切れる約数が見つかった瞬間にbreakでループを抜けるため、計算量が減る
• printで表示する代わりにreturnでリストを返すため、関数の再利用性が高い

方法3：平方根を使ってさらに高速化する

ここで重要な数学的性質があります。n が素数でない場合、n の約数のうち少なくとも1つは √n（nの平方根）以下になるというものです。つまり、2から n-1 まで全部調べなくても、√n まで調べれば十分ということになります。

この性質を利用すると、探索範囲を int(pr ** 0.5) + 1 まで絞り込めます。

サンプルコード

def primemethod3(number):
    # 結果を格納するリストを初期化
    primes = []
    for pr in range(2, number):
        isPrime = True
        for num in range(2, int(pr ** 0.5) + 1):
            if pr % num == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(pr)
            print("Prime number: ", pr)

primemethod3(50)

出力結果

Prime number:  2
Prime number:  3
Prime number:  5
Prime number:  7
Prime number:  11
Prime number:  13
Prime number:  17
Prime number:  19
Prime number:  23
Prime number:  29
Prime number:  31
Prime number:  37
Prime number:  41
Prime number:  43
Prime number:  47

まとめ：どの方法を選ぶべきか？

3つの方法はいずれも同じ結果を出しますが、処理効率は方法1 ＜ 方法2 ＜ 方法3の順に向上します。Pythonで素数を求める場合は、平方根まで調べる方法3をベースにするのがおすすめです。さらに大規模な範囲を扱いたい場合には、エラトステネスのふるいなどのアルゴリズムも検討するとよいでしょう。