在数学领域中，质数(素数)是具有特殊性质的整数。质数是指大于 1 且除了 1 和它自身外，不能被其他自然数整除的数。在编程中，判断一个数是否为质数是一个常见的问题，而 Python 作为一种功能强大的编程语言，提供了多种方法来实现这个功能。本文站长工具网将详细介绍 Python 判断质数的几种方法，并对每种方法进行分析和比较。
一、质数的定义和性质
(一)定义
质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。例如，2、3、5、7、11 等都是质数，而 4、6、8、9、10 等则不是质数，因为它们可以被除了 1 和自身以外的其他数整除。
(二)性质
质数只有两个因数：1 和它本身。
质数是无限的。欧几里得在其《几何原本》中最早证明了质数的无限性。
除了 2 以外，所有的质数都是奇数。这是因为如果一个数是偶数，那么它必然能被 2 整除，所以除了 2 以外的偶数都不是质数。
二、Python 判断质数的方法
(一)基本方法：试除法
原理
试除法是判断质数最基本的方法。其原理是对于一个给定的数 n，从 2 开始，依次用 n 除以每个小于等于 n 的整数，如果在这个过程中找到一个数能够整除 n，那么 n 就不是质数;如果直到 n 的平方根都没有找到这样的数，那么 n 就是质数。
例如，要判断 17 是否为质数，从 2 开始，依次用 17 除以 2、3、4、5、6、7、8(8 是 17 的平方根的整数部分)，发现没有一个数能够整除 17，所以 17 是质数。
代码实现
def is_prime(n): if n < 2: return False sqrt_n = int(n**0.5) + 1 for i in range(2, sqrt_n): if n % i == 0: return False return True
首先，判断输入的数 n 是否小于 2，如果是，则直接返回 False，因为质数是大于 1 的自然数。
然后，计算 n 的平方根的整数部分并加 1，得到循环的上限 sqrt_n。
最后，从 2 开始到 sqrt_n，依次用 n 除以每个数，如果找到一个数能够整除 n，就返回 False;如果循环结束都没有找到这样的数，就返回 True。
分析
优点：
原理简单易懂，容易实现。
对于较小的数，判断速度较快。
缺点：
当判断较大的数时，效率较低，因为需要进行较多的除法运算。
(二)优化的试除法
原理
在基本的试除法基础上，可以进行一些优化。由于除了 2 以外的偶数都不是质数，所以在判断一个数 n 是否为质数时，可以先判断 n 是否为 2，如果是，直接返回 True;如果不是，再判断 n 是否为偶数，如果是偶数，直接返回 False。然后，从 3 开始，每次增加 2(只考虑奇数)，依次用 n 除以这些奇数，直到 n 的平方根。
例如，要判断 25 是否为质数，首先判断它不是 2，然后发现它是奇数，从 3 开始，依次用 25 除以 3、5、7(7 是 25 的平方根的整数部分)，发现 25 可以被 5 整除，所以 25 不是质数。
代码实现
def is_prime_optimized(n): if n < 2: return False if n == 2: return True if n % 2 == 0: return False sqrt_n = int(n**0.5) + 1 for i in range(3, sqrt_n, 2): if n % i == 0: return False return True
首先，和基本方法一样，判断 n 是否小于 2，如果是，返回 False;如果 n 等于 2，返回 True;如果 n 是偶数，返回 False。
然后，计算 n 的平方根的整数部分并加 1，得到循环的上限 sqrt_n。
最后，从 3 开始，每次增加 2，依次用 n 除以这些奇数，如果找到一个数能够整除 n，就返回 False;如果循环结束都没有找到这样的数，就返回 True。
分析
优点：
比基本的试除法更加高效，因为减少了一半的循环次数。
对于较大的数，判断速度也有一定的提升。
缺点：
仍然需要进行较多的除法运算，当判断非常大的数时，效率还是不够高。
(三)埃拉托斯特尼筛法
原理
埃拉托斯特尼筛法是一种古老而有效的筛选质数的方法。其原理是先列出从 2 开始的所有自然数，然后从第一个质数 2 开始，把它的倍数都标记为合数，接着再找到下一个未被标记的数，这个数就是新的质数，再把它的倍数标记为合数，如此重复，直到所有的数都被处理过。
例如，要找出小于 100 的质数，首先列出 2 到 99 的所有数。从 2 开始，把 2 的倍数(4、6、8、…、98)都标记为合数。然后找到下一个未被标记的数 3，把 3 的倍数(6、9、12、…、99)都标记为合数。接着找到下一个未被标记的数 5，把 5 的倍数(10、15、20、…、95)都标记为合数，以此类推，直到所有小于等于 100 的数都被处理过，剩下的未被标记的数就是质数。
代码实现
def sieve_of_eratosthenes(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = 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 primes = [i for i in range(n + 1) if is_prime[i]] return primes
首先，创建一个长度为 n + 1 的布尔列表 is_prime，初始值都为 True，表示所有的数都可能是质数。然后，将 0 和 1 标记为 False，因为它们不是质数。
接着，从 2 开始到 n 的平方根，对于每个质数 i，如果 is_prime [i] 为 True，就把它的倍数(从 i * i 开始，因为小于 i * i 的倍数已经在前面的循环中被标记过了)都标记为 False。
最后，遍历 is_prime 列表，将所有值为 True 的索引(即质数)收集到一个列表 primes 中并返回。
分析
优点：
可以一次性找出一定范围内的所有质数，而不仅仅是判断一个数是否为质数。
对于较大范围的质数筛选，效率非常高。
缺点：
需要占用一定的内存空间来存储布尔列表。
如果只需要判断一个数是否为质数，相对来说有点大材小用。
(四)费马小定理
原理
费马小定理是数论中的一个重要定理，其内容为：如果 p 是一个质数，且 a 是任何整数，那么 a 的 p 次方减去 a 是 p 的倍数。用数学公式表示为 a^p ≡ a (mod p)。反过来，如果对于一个数 n，存在一个整数 a，使得 a 的 n 次方减去 a 不是 n 的倍数，那么 n 就不是质数。
例如，要判断 17 是否为质数，可以选择 a = 2，计算 2 的 17 次方减去 2，即 2^17 - 2 = 131070，而 131070 除以 17 的余数为 0，所以根据费马小定理，17 可能是质数。但这只是一个初步的判断，因为费马小定理是一个必要条件而不是充分条件，也就是说，如果一个数满足费马小定理，它可能是质数，但不一定是质数。为了提高准确性，可以进行多次测试，选择不同的 a 值。
代码实现
import random def is_prime_fermat(n, k=5): if n < 2: return False if n == 2 or n == 3: return True if n % 2 == 0: return False for _ in range(k): a = random.randint(2, n - 2) if pow(a, n - 1, n)!= 1: return False return True
首先，判断输入的数 n 是否小于 2，如果是，返回 False;如果 n 等于 2 或 3，返回 True;如果 n 是偶数，返回 False。
然后，进行 k 次测试。每次测试中，随机选择一个整数 a，范围是 2 到 n - 2。计算 a 的 n - 1 次方对 n 取余，如果结果不等于 1，说明 n 不是质数，直接返回 False。
如果经过 k 次测试都没有返回 False，那么就认为 n 可能是质数，返回 True。
分析
优点：
对于较大的数，判断速度相对较快。
通过多次测试，可以提高判断的准确性。
缺点：
仍然不能完全确定一个数是否为质数，只是提供了一种较高概率的判断方法。
需要使用随机数生成器，可能存在一定的随机性。
(五)米勒 - 拉宾素性检验
原理
米勒 - 拉宾素性检验是一种基于费马小定理的改进算法，用于高效地判断一个大数是否为质数。其原理是通过随机选择多个基值进行测试，如果一个数在多次测试中都表现得像一个质数，那么它很可能是质数。
具体来说，对于给定的数 n，首先将 n - 1 表示为 2 的幂次方乘以一个奇数 r，即 n - 1 = 2^s * r。然后，随机选择一个整数 a，范围是 2 到 n - 2。计算 y = a^r mod n，如果 y 等于 1 或 n - 1，那么 n 可能是质数。如果 y 不等于 1 也不等于 n - 1，那么继续计算 y 的平方，即 y^2 mod n，如果 y 的平方等于 n - 1，那么 n 可能是质数;否则，继续计算 y 的平方，直到计算 s 次为止。如果在这个过程中没有找到 y 的值等于 n - 1，那么 n 就不是质数。
例如，要判断 17 是否为质数，首先将 17 - 1 = 16 表示为 2 的 4 次方乘以 1，即 s = 4，r = 1。随机选择 a = 3，计算 3^1 mod 17 = 3，不等于 1 也不等于 16。继续计算 3^2 mod 17 = 9，不等于 16。计算 3^4 mod 17 = 16，所以根据米勒 - 拉宾素性检验，17 可能是质数。同样，为了提高准确性，可以进行多次测试。
代码实现
import random def miller_rabin(n, k=5): if n < 2: return False if n == 2 or n == 3: return True if n % 2 == 0: return False r, s = 0, n - 1 while s % 2 == 0: r += 1 s //= 2 for _ in range(k): a = random.randint(2, n - 2) y = pow(a, s, n) if y == 1 or y == n - 1: continue for _ in range(r - 1): y = pow(y, 2, n) if y == n - 1: break else: return False return True
首先，和费马小定理的代码一样，进行一些基本的判断，如判断 n 是否小于 2、是否等于 2 或 3、是否为偶数等。
然后，计算 n - 1 的 2 的幂次方表示，即找到 r 和 s，使得 n - 1 = 2^s * r。
接着，进行 k 次测试。每次测试中，随机选择一个整数 a，计算 y = a^s mod n。如果 y 等于 1 或 n - 1，继续下一次测试;如果 y 不等于 1 也不等于 n - 1，继续计算 y 的平方，直到计算 r - 1 次为止。如果在这个过程中没有找到 y 的值等于 n - 1，那么返回 False;如果所有的测试都通过，返回 True。
分析
优点：
对于非常大的数，判断速度非常快，比费马小定理更加准确。
通过多次测试，可以进一步提高准确性。
缺点：
代码相对复杂，理解起来有一定难度。
仍然不能完全确定一个数是否为质数，但在实际应用中，其准确性已经非常高。
三、方法比较与选择
(一)效率比较
对于较小的数(小于 1000)，基本的试除法和优化的试除法速度较快，因为这些方法的计算量相对较小。埃拉托斯特尼筛法在这个范围内的效率优势不明显，因为它主要用于筛选较大范围内的质数。费马小定理和米勒 - 拉宾素性检验在判断较小的数时，由于需要进行随机数生成和多次计算，效率可能不如试除法。
对于较大的数(大于 100000)，埃拉托斯特尼筛法可以一次性筛选出一定范围内的所有质数，效率较高。费马小定理和米勒 - 拉宾素性检验也表现出较好的性能，因为它们可以快速地进行大数的判断。而试除法在判断较大的数时，效率会显著下降，因为需要进行大量的除法运算。
(二)准确性比较
基本的试除法和优化的试除法在判断质数时是准确的，但对于非常大的数，由于计算量较大，可能会出现超时或错误的情况。
埃拉托斯特尼筛法可以准确地筛选出一定范围内的所有质数，但如果只需要判断一个数是否为质数，可能会显得有些浪费资源。
费马小定理和米勒 - 拉宾素性检验在大多数情况下是准确的，但不能完全保证一个数是质数。然而，通过多次测试，可以提高准确性。
(三)适用场景
如果只需要判断一个较小的数是否为质数，并且对效率要求较高，可以使用基本的试除法或优化的试除法。
如果需要筛选一定范围内的所有质数，或者需要对较大范围的数进行质数判断，可以使用埃拉托斯特尼筛法。
如果需要快速判断一个非常大的数是否为质数，可以使用费马小定理或米勒 - 拉宾素性检验，并进行多次测试以提高准确性。
总结
Python 提供了多种方法来判断一个数是否为质数，每种方法都有其特点和适用场景。基本的试除法和优化的试除法简单易懂，适用于较小的数;埃拉托斯特尼筛法适用于筛选一定范围内的所有质数;费马小定理和米勒 - 拉宾素性检验适用于快速判断较大的数是否为质数。在实际应用中，可以根据具体的需求选择合适的方法。同时，需要注意的是，虽然这些方法在大多数情况下是准确的，但不能完全保证一个数是质数，特别是对于非常大的数。在需要高度准确性的情况下，可以结合多种方法进行判断，或者使用更专业的数学软件和算法。
本文由@战地网 原创发布。
该文章观点仅代表作者本人，不代表本站立场。本站不承担相关法律责任。
如若转载，请注明出处：https://www.zhanid.com/biancheng/1989.html
