Python

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

この記事では、Pythonで素数を判定したり、生成したりする方法を解説します。素数とは、1以外の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

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

from sympy import isprime

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

実行結果

2
3
5
7
11
13
17
19

2の64乗以降の数は疑似素数が含まれる可能性がある

素数のリストを生成する

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

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 =  [i for i in sieve.primerange(20)]
print(primes)

実行結果

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

まとめ

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

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

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

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

『DMM WEBCAMP COMMIT』