Pythonで素数を見つける3つの方法と実行速度の徹底比較

はじめに

このチュートリアルでは、Pythonで素数を見つけるための複数の手法を取り上げ、それぞれにかかる実行時間を実際に計測して比較します。計測にはPython標準ライブラリのtimeモジュールを使用します。同じ処理でも書き方を少し工夫するだけで実行速度が大きく変わることを、コード例とともに確認していきましょう。

方法1：基本の総当たり法

もっとも一般的な素数判定の方法です。2からn-1までのすべての整数で順番に割り切れるかを調べます。

• 数値が1以下の場合はFalseを返します（1は素数ではないため）。
• ループ中に割り切れる数（約数）が見つかったら、その時点でFalseを返します。
• ループを最後まで抜けられた場合のみ、Trueを返します。

コード例

# timeモジュールをインポート
import time

# 素数かどうかを判定する関数
def is_prime(n):
    if n <= 1:
        return False
    else:
        for i in range(2, n):
            # 約数が存在するかチェック
            if n % i == 0:
                # 素数ではないのでFalseを返す
                return False
        # 素数なのでTrueを返す
        return True

# 計測開始
start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1
print(f'素数の総数: {primes}')
# 計測終了
end_time = time.time()
print(f'実行時間: {end_time - start_time}')

実行結果

素数の総数: 9592
実行時間: 63.1301212310791

上記のプログラムを実行すると、100000未満の範囲に9592個の素数が存在することがわかります。しかし、すべての数に対して2からn-1までを順に調べているため、実行に1分以上かかってしまいます。これでは実用性に欠けると言えるでしょう。

方法2：平方根まで調べることで高速化

nが合成数（素数ではない数）の場合、n = a × b と表せます。このとき、aとbの少なくとも一方は必ず√n以下になります。つまり2から√nまでの整数だけを調べれば十分であり、これにより反復回数を大幅に削減できます。

コード例

# timeモジュールをインポート
import time
# sqrt関数を使うためにmathモジュールをインポート
import math

# 素数かどうかを判定する関数
def is_prime(n):
    if n <= 1:
        return False
    else:
        # nの平方根までループを回す
        for i in range(2, int(math.sqrt(n)) + 1):
            # 約数が存在するかチェック
            if n % i == 0:
                # 素数ではないのでFalseを返す
                return False
        # 素数なのでTrueを返す
        return True

# 計測開始
start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1
print(f'素数の総数: {primes}')
# 計測終了
end_time = time.time()
print(f'実行時間: {end_time - start_time}')

実行結果

素数の総数: 9592
実行時間: 0.2039644718170166

方法1と比べて実行時間が約300分の1に短縮されました。探索範囲を平方根までに限定するだけで、劇的な高速化が実現できています。

方法3：偶数を除外してさらに高速化

方法2では偶数も含めてすべての数を調べていましたが、偶数に素数は2しか存在しないという性質があります。そこで、2の判定だけ特別扱いし、それ以降は奇数のみを候補として調べることで、無駄な計算をさらに減らします。

コード例

# timeモジュールをインポート
import time
# sqrt関数を使うためにmathモジュールをインポート
import math

# 素数かどうかを判定する関数
def is_prime(n):
    # 1以下は素数ではない
    if n <= 1:
        return False
    # 2は素数
    elif n == 2:
        return True
    # 2より大きい偶数は素数ではない
    elif n > 2 and n % 2 == 0:
        return False
    else:
        # 3からnの平方根まで、ステップ2で奇数のみを調べる
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            # 約数が存在するかチェック
            if n % i == 0:
                # 素数ではないのでFalseを返す
                return False
        # 素数なのでTrueを返す
        return True

# 計測開始
start_time = time.time()
primes = 0
for i in range(100000):
    if is_prime(i):
        primes += 1
print(f'素数の総数: {primes}')
# 計測終了
end_time = time.time()
print(f'実行時間: {end_time - start_time}')

実行結果

素数の総数: 9592
実行時間: 0.10342741012573242

偶数の判定をスキップしただけで、方法2からさらに約半分の時間で処理が完了しました。

実行時間の比較まとめ

※実行時間はマシンの性能や環境によって変動するため、あくまで目安としてお考えください。

まとめ

今回紹介したように、探索範囲の削減や無駄な候補の除外といったアルゴリズムの改善を重ねることで、素数判定の処理速度は数百倍以上速くなります。さらに広い範囲の素数を一括で求めたい場合は、古典的かつ高効率な「エラトステネスの篩」の活用も検討してみてください。

チュートリアルに関するご質問や不明な点があれば、コメント欄でお気軽にお知らせください。