用Fermat素性判定方法代码

Fermat素性判定法，也称为费马小定理，是一种非确定性的算法，用于判断一个大于1的整数是否可能是质数。该方法基于费马大定理，即如果p是一个质数，对于任意整数a (1 < a < p)，都有\(a^{p-1} \equiv 1 \mod p\)。

以下是使用Python实现的一个简单版本的Fermat素性测试：

def fermat_test(n, k=5):  # 默认测试5次，k值越大，验证越准确但时间更长
    if n <= 1 or n == 4:  # 特殊情况，2和4不是质数，直接返回False
        return False
    if n % 2 == 0:  # 如果n是偶数，除了2外不可能是质数，除了2的其它偶数都可以简化测试
        return n > 2

    for _ in range(k):
        a = random.randint(2, n - 2)  # 随机选取[2, n-2]范围内的整数
        if pow(a, n - 1, n) != 1:  # 如果计算结果不等于1 mod n，则n可能是合数
            return False
    return True  # 经过多次测试都通过，可能很大概率上n是质数，但并不能保证

# 使用示例
n = int(input("请输入一个正整数："))
result = fermat_test(n)
if result:
    print(f"{n}可能是质数")
else:
    print(f"{n}可能是合数")