Pythonのgmpy2モジュールを使用して素数を判定する方法

1. 素朴な方法: 最も基本的な素数判定の方法は、対象の数値を2からその平方根までの数で割って割り切れるかどうかを調べることです。以下は、この方法をgmpy2を使用して実装した例です。

import gmpy2
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(gmpy2.isqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
# 使用例
print(is_prime(17))  # True
print(is_prime(21))  # False

2. Miller-Rabinテスト: Miller-Rabinテストは、確率的な素数判定法であり、高速に動作します。以下は、gmpy2を使用してMiller-Rabinテストを行う例です。

import gmpy2
def is_prime_miller_rabin(n, k=10):
    return gmpy2.is_prime(n, k)
# 使用例
print(is_prime_miller_rabin(17))  # True
print(is_prime_miller_rabin(21))  # False

3. Lucas-Lehmerテスト (メルセンヌ素数の判定): メルセンヌ素数は特殊な形式の素数であり、Lucas-Lehmerテストを使用して効率的に判定することができます。以下は、gmpy2を使用してLucas-Lehmerテストを行う例です。

import gmpy2
def is_mersenne_prime(p):
    if p < 2:
        return False
    m = 2  p - 1
    return gmpy2.is_prime(m)
# 使用例
print(is_mersenne_prime(5))  # True (2^5 - 1 = 31 is prime)
print(is_mersenne_prime(6))  # False

これらはいくつかの素数判定の方法の一部ですが、gmpy2モジュールには他にもさまざまな素数関連の機能があります。詳細な情報や他の利用可能な関数については、gmpy2の公式ドキュメントを参照してください。

以上が、Pythonのgmpy2モジュールを使用して素数を判定する方法に関する解説とコード例です。