在Python中如何编写一个函数来判断一个数是否为质数？
判断一个数是否为质数是一种经典的算法问题，对于初学Python编程的人来说可以作为练手的题目。本文我们将从数学角度分析质数的定义，以及介绍几种常用的判断方法，最后给出Python实现判断一个数是否为质数的函数。
一、质数的定义
质数是指只能被1和它本身整除的正整数。比如2、3、5、7、11等就是质数，而4、6、8、9等都不是。
质数的特性为：
① 只能被1和它本身整除，除此之外再不能被其它数整除；
② 除了1和本身，不存在其它公因数；
③ 任何一个合数都可以表示成一些质数的积。
二、判断质数的方法
1. 暴力枚举判断法
暴力枚举判断法是一种最朴素的方法，既直观易懂，但是时间复杂度比较高，容易超时。
具体做法：遍历[2, n - 1]之间所有的数，判断n是否能被整除。如果找到能够整除的数，则说明n不是质数；若找不到的话，则说明n是质数。
代码实现如下：
def naive_is_prime(n):
"""暴力枚举判断法"""
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
2. 按质数定义算法
按照定义，可以直接使用if语句判断：
def is_prime(n):
"""按质数定义算法"""
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
3. 埃拉托色尼筛法
埃拉托色尼筛法（Sieve of Eratosthenes）是一种简单而又有效的判断质数方法。这种方法的基本思想是：从2开始，将每个质数的倍数都标记成合数，即将它们排除掉。如此一来，留下的就是所有的质数。
具体流程：
① 构建一个长度为n+1的列表，并初始化每个元素都为True；
② 从2开始依次枚举每个质数，并将它的倍数都标记为False，因为它们不是质数；
③ 数组中留下来的都是质数了。
代码实现如下：
def sieve_is_prime(n):
"""埃拉托色尼筛法"""
if n < 2:
return False
is_prime = [True] * (n + 1)
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 is_prime[n]
三、Python实现判断质数的函数
基于以上3种方法，我们可以写出Python实现判断质数的函数：
def is_prime(n):
"""判断一个数是否为质数"""
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def sieve_is_prime(n):
"""埃拉托色尼筛法"""
if n < 2:
return False
is_prime = [True] * (n + 1)
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 is_prime[n]
四、简化函数实现
在Python中，我们可以使用all()函数将简单的for循环判断简化为一行代码：
def is_prime(n):
"""判断一个数是否为质数"""
return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))
这段代码的表达式 all(n % i for i in range(2, int(n ** 0.5) + 1)) 判断了是否存在能够整除n的i。
五、测试函数正确性
我们使用Python内置的unittest框架进行简单的测试。
import unittest
class Test(unittest.TestCase):
def test_is_prime(self):
"""测试常规质数"""
self.assertTrue(is_prime(2))
self.assertTrue(is_prime(3))
self.assertTrue(is_prime(5))
self.assertTrue(is_prime(7))
self.assertTrue(is_prime(11))
def test_sieve_is_prime(self):
"""测试常规质数"""
self.assertTrue(sieve_is_prime(2))
self.assertTrue(sieve_is_prime(3))
self.assertTrue(sieve_is_prime(5))
self.assertTrue(sieve_is_prime(7))
self.assertTrue(sieve_is_prime(11))
def test_not_is_prime(self):
"""测试非质数"""
self.assertFalse(is_prime(1))
self.assertFalse(is_prime(4))
self.assertFalse(is_prime(6))
self.assertFalse(is_prime(10))
self.assertFalse(is_prime(20))
def test_not_sieve_is_prime(self):
"""测试非质数"""
self.assertFalse(sieve_is_prime(1))
self.assertFalse(sieve_is_prime(4))
self.assertFalse(sieve_is_prime(6))
self.assertFalse(sieve_is_prime(10))
self.assertFalse(sieve_is_prime(20))
if __name__ == '__main__':
unittest.main()
六、总结
本文介绍了常见的几种判断质数的方法，并着重介绍了暴力枚举法、按质数定义法和埃拉托色尼筛法，并详细阐述了它们的基本原理和代码实现。通过Python实现判断一个数是否为质数的函数，我们可以发现Python对于判断质数非常方便。最后使用Python内置的unittest框架进行简单测试，验证了函数正确性。