Python中判断质数的方法有很多种，其中比较常用的是试除法和埃氏筛法。试除法是指对于一个数n，从2到n-1逐个判断是否能整除n，如果都不能整除，则n为质数。而埃氏筛法则是利用筛子的思想，从2开始，把每个质数的倍数都标记成合数，直到筛子中的所有数都被标记过为止，剩下的未被标记的数即为质数。

_x000D_

下面我们来看一下Python中如何实现这两种方法。

_x000D_

## 试除法

_x000D_

`python

_x000D_

def is_prime(n):

_x000D_

if n < 2:

_x000D_

return False

_x000D_

for i in range(2, n):

_x000D_

if n % i == 0:

_x000D_

return False

_x000D_

return True

_x000D_ _x000D_

这里我们先判断n是否小于2，因为质数定义为大于1的自然数。然后从2开始逐个判断是否能整除n，如果能整除，则n不是质数，返回False；如果都不能整除，则n是质数，返回True。

_x000D_

## 埃氏筛法

_x000D_

`python

_x000D_

def primes(n):

_x000D_

is_prime = [True] * (n + 1)

_x000D_

is_prime[0] = is_prime[1] = False

_x000D_

for i in range(2, int(n ** 0.5) + 1):

_x000D_

if is_prime[i]:

_x000D_

for j in range(i * i, n + 1, i):

_x000D_

is_prime[j] = False

_x000D_

return [i for i in range(2, n + 1) if is_prime[i]]

_x000D_ _x000D_

这里我们先创建一个长度为n+1的布尔型数组is_prime，用来记录每个数是否为质数。然后将0和1的位置标记为False，因为它们不是质数。接着从2开始循环到n的平方根，如果is_prime[i]为True，说明i是质数，我们就将i的倍数都标记为False。最后返回is_prime中值为True的位置，即为质数。

_x000D_

问答扩展：

_x000D_

1. 什么是质数？

_x000D_

- 答：质数是指只能被1和自身整除的自然数，大于1的自然数中，只有2、3、5、7、11等为质数，其他数都可以分解成质数的乘积。

_x000D_

2. 试除法的时间复杂度是多少？

_x000D_

- 答：试除法的时间复杂度为O(n)，即需要判断n个数是否为质数，每个数需要循环n-2次。

_x000D_

3. 埃氏筛法的时间复杂度是多少？

_x000D_

- 答：埃氏筛法的时间复杂度为O(nloglogn)，即需要循环到n的平方根，每个数最多被标记一次。

_x000D_

4. 如何判断一个数是否为质数的最优算法是什么？

_x000D_

- 答：目前最优的算法是Miller-Rabin素性检验，时间复杂度为O(klog^3n)，其中k为检验次数，n为待检验数。该算法是基于费马小定理和随机化思想的，可以高效地判断一个数是否为质数。

_x000D_