python如何求质数

我们可以使用以下两种方法来判断一个数是否是质数：

方法1：暴力遍历法

我们可以遍历从2到$n-1$的所有数，判断是否能整除$n$。如果存在一个能整除$n$的数，则$n$不是质数；否则$n$是质数。

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

方法2：优化的方法

在暴力遍历法中，我们只需要判断$n$是否能被从2到$\sqrt{n}$的数整除即可。因为如果存在一个大于$\sqrt{n}$的因子，那么必然存在一个小于$\sqrt{n}$的因子。所以只需要判断到$\sqrt{n}$即可。

import math
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True

使用这两种方法，你可以判断一个数是否是质数。例如，调用is_prime(17)会返回True，因为17是质数。