Python判断质数方法用法介绍

本文将介绍如何用Python判断一个数是否为质数。其中，我们将从多个方面进行阐述，包括质数的定义、判断方法、算法优化等内容，希望对Python初学者或对质数感兴趣的读者有所帮助。

一、什么是质数

质数也称素数，是指在大于1的正整数中，只能被1和该数本身整除的数。比如2、3、5、7、11、13等都是质数，而4、6、8、9、10等则不是质数。

之所以叫质数，是因为质数本身不能再拆分成不同的乘积形式，只有1和该数本身两个因数。这种被分解为质数乘积表示的形式，称为质因数分解。

质数在密码学领域有广泛应用，因为大质数的因数分解是计算机科学中的困难问题之一。

二、判断质数的方法

方法一：试除法

试除法是判断质数最简单的方法，即判断一个数n能否被2到n-1中的任意一个数整除。如果都不能整除，则n为质数。这种方法容易实现，但计算量大，效率较低。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

上述代码中，从2到n-1依次用n去除，如果有任何一个数能够整除，则返回False，表示n不是质数。否则返回True，表示n是质数。

方法二：优化试除法

试除法的计算量较大，可以进行优化。通过观察发现，如果一个数n不能被2至$\sqrt{n}$间的整数整除，那么，它也肯定不能被$\sqrt{n}$到n-1间的整数整除。因此，在试除法中，只需要试除至$\sqrt{n}$即可。

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

上述代码中，将n开方后找到整数位，并从2到整数位进行试除。这种算法优化之后，计算量相对减少，但仍存在效率问题。

方法三：埃氏筛法

埃氏筛法用于求解给定范围内的所有质数。具体实现方法是：先用2到n-1中的每一个数去除2，标记被整除的数，然后再用下一个未被标记的数3去除它未被标记的倍数，依次进行下去，直到最后，剩下的未被标记的数就是质数。

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i, val in enumerate(is_prime) if val]

print(primes(100))

上述代码中，使用一个列表is_prime记录每个数是否是质数，初始都为True。从2开始遍历列表，如果这个数是质数，则将它的倍数都标记为False。最后返回is_prime中为True的数，即为质数。

三、算法优化

对于计算质数问题，算法优化是个重要的议题。下面介绍两种优化方式。

方式一：判断奇数

一个数如果是偶数且不是2，则它肯定不是质数。因此，如果一开始判断出一个数是偶数，则立刻返回False，避免后面的不必要计算。

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

上述代码中，在判断前先特殊处理2和小于2的数，然后跳过所有的偶数试除。

方式二：Miller-Rabin算法

Miller-Rabin算法是一种分治算法，用于判断一个数是否是质数。由于Miller-Rabin算法具有高效性和准确性，因此它被广泛应用于RSA等密码学算法中。

Miller-Rabin算法基于一个重要定理：如果n是一个质数，那么对于任意整数a，有$a^{n-1}\equiv1 \pmod n$。该定理称为费马小定理(Fermat’s little theorem)。基于该定理，可以发展出Miller-Rabin算法的伪代码如下：

1. 将n-1分解成$2^s \cdot d$的形式
2. 针对每一个a，重复k次：
   a. 生成随机数a，2<=a<=n-2；
   b. 计算$x_0 = a^d \pmod n$
   c. 对于r = 0至s-1，计算$x_r$ = $x_{r-1}^2 \pmod n$;
      如果$x_r = 1$且$r!=(s-1)$，则返回False
      如果$x_s != 1$，则返回False
      如果$x_s = 1$，则返回True

上述算法的关键在于计算$a^d \pmod n$和$x_{r-1}^2 \pmod n$的过程，使用了模幂运算，可参考Python内置函数pow的实现方式。Miller-Rabin算法的准确性与其迭代次数有关，可以设计固定的迭代次数得到较高的正确性，但无法证明其完全正确。

import random

def is_prime(n, k=5):
    if n < 2: 
        return False
    if n == 2 or n == 3: 
        return True
    if n % 2 == 0: 
        return False
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2
    for i in range(k):
        a = random.randint(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

print(is_prime(23))

上述代码中，使用了Python内置函数pow进行模幂运算，通过计算多组随机数，判断是否为质数。可以自定义迭代次数k来调整准确性和效率。

四、总结

本文介绍了Python判断质数的方法，包括试除法、优化试除法、埃氏筛法和Miller-Rabin算法。其中，优化试除法和埃氏筛法更高效、更可靠。在实际使用中，可根据具体需求选择合适的算法并根据实际情况进行代码优化。同时，也可以通过本文的介绍来深入理解质数的性质和计算方法。

原创文章，作者：DWQRD，如若转载，请注明出处：https://www.506064.com/n/373315.html