【Python】素数を判定したり、生成したりする方法

この記事では、Pythonで素数を判定したり、生成したりする方法を解説します。

素数とは、1以外の1と自分自身でしか割り切れない自然数のことを言います。

それでは、素数を扱う方法を見ていきましょう！

素数を判定する

それではまずは、素数を判定する方法を見ていきましょう！

自作の関数で判定する

素数は以下のようなコードで判定することができます。

def isprime(n: int) -> bool:

    # 1以下は素数ではないので排除
    if n <= 1:
        return False

    # 2からnの2分の1乗までのループ
    for x in range(2, int(n ** 0.5) + 1):
        if n % x == 0:
            # 割り切れる値があれば素数ではないのでFalseを返す
            return False
    # ここまでくれば素数
    return True

試しに 0 ~ 100 までの素数を出力してみます。

for i in range(20):
    if isprime(i):
        print(i)

実行結果

2
3
5
7
11
13
17
19

あらかじめ偶数を排除する方法もある。

def isprime(n: int) -> bool:
    if (n < 2): return False
    elif (n == 2): return True
    elif (n % 2 == 0): return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

SymPyで判定する

SymPyとは、記号計算を行うためのライブラリです。素数の他にも因数分解や微分、積分など色々な計算を行うことができます。

SymPyはpipでインストールすることができます。

pip install sympy

pipを使ってパッケージ管理する方法

素数かどうかを判定するには、isprime()関数を使う。

from sympy import isprime

for i in range(20):
    if isprime(i):
        print(i)

実行結果

2
3
5
7
11
13
17
19

SymPyには、素数を取得する関数が他にもたくさん用意されている。

import sympy

# n番目の素数を返す
sympy.prime(1)   # 2
sympy.prime(2)   # 3
sympy.prime(10)  # 29

# nまでの素数の数
sympy.primepi(2)   # 1
sympy.primepi(5)   # 3
sympy.primepi(20)  # 8

LinkNumber Theory — SymPy 1.9 documentation

素数のリストを生成する

先ほど作成した関数と内包表記を組み合わせることで素数のリストを生成することができる。

def ispirme(n: int) -> bool:

    if n <= 1: return False

    for x in range(2, int(n ** 0.5) + 1):
        if n % x == 0:
            return False
    return True

# 素数のリスト
primes = [i for i in range(20) if ispirme(i)]
print(primes)

実行結果

[2, 3, 5, 7, 11, 13, 17, 19]

Sympyが使える状況ならprimerange()を使うともっと簡単に任意の範囲の素数のリストを生成できる。

from sympy import sieve

primes = list(sieve.primerange(20))
print(primes)

実行結果

[2, 3, 5, 7, 11, 13, 17, 19]

まとめ

この記事では、Pythonで素数を判定したり素数のリストを生成する方法を解説しました。

素数は、RSA暗号に使われたりします。RSA暗号とは、素因数分解にとても時間がかかることを利用した暗号化方法です。

外部RSA暗号とは？仕組みや応用事例を初心者にもわかりやすく解説！｜ITトレンド

それでは今回の内容はここまでです。ではまたどこかで〜( ・∀・)ﾉ