Python快速判断质数的四种方法

本文将阐述Python中快速判断质数的四种方法，分别是试除法、素数定理、费马小定理以及Miller-Rabin算法。

一、试除法

试除法是最简单、最朴素的方法，即对一个数n，用2到sqrt(n)范围内的所有整数去除一遍，如果都不能被整除，那么n就是质数。

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

以上代码中，我们用range函数来生成从2到sqrt(n)的范围，对于每个整数i，如果n能够被i整除，那么n就不是质数，返回False，否则继续循环。如果循环结束，都没有返回False，那么n就是质数，返回True。

二、素数定理

素数定理是一种通过估算质数个数来判断质数的方法，公式为：对于一个数n，当n趋向于无穷大时，小于n的质数的个数约为n/ln(n)。

根据以上公式，我们可以估算出n附近质数的个数，然后通过试除法判断n是否为质数。

import math

def is_prime(n):
    if n == 1:
        return False
    # 根据素数定理估算质数个数
    prime_count = n // math.log(n)
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

以上代码中，我们先根据素数定理估算出n附近质数的个数，然后再用试除法来判断n是否为质数。

三、费马小定理

费马小定理是一种基于模运算的方法，公式为：如果p是质数，a是p的倍数，那么a^p-1模p等于1。

根据以上公式，我们可以得到以下代码：

import random

def is_prime(n):
    if n == 1:
        return False
    # 判断经过若干次测试后，n是否为质数的概率趋于1
    for i in range(5):
        a = random.randint(1, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    return True

以上代码中，我们对于n进行若干次费马小定理测试，每次取一个1到n-1的随机数a，如果a^(n-1) % n不等于1，那么n就不是质数，否则继续循环。如果循环结束都没有返回False，那么n就是质数，返回True。

四、Miller-Rabin算法

Miller-Rabin算法是一种基于模算术的概率性质数判断算法，其原理是判断n是否为一个合数。它需要选取一个适合的整数k和一些整数r，s，使n-1 = 2^s*r。

根据Miller-Rabin算法的原理，我们可以得到以下代码：

import random

def witness(a, n):
    # 先计算出n-1能分解成2的多少次幂和一个奇数r
    r, s = n - 1, 0
    while r % 2 == 0:
        s += 1
        r //= 2
    # 利用模算术判断a是否为n的证人
    x = pow(a, r, n)
    for j in range(s):
        y = pow(x, 2, n)
        if y == 1 and x != 1 and x != n - 1:
            return True   # a是n的真证人
        x = y
    if x != 1:
        return True   # a是n的真证人
    return False

def is_prime(n):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    # 利用多次随机测试，计算n是否为合数
    for i in range(20):
        a = random.randint(1, n - 1)
        if witness(a, n):
            return False
    return True

以上代码中，我们先计算出n-1能分解成2的多少次幂和一个奇数r，然后利用模算术来判断a是否为n的证人，如果a是n的真证人，那么n就一定是合数。我们用20次随机测试来判断n是否为合数。