我们可以使用以下两种方法来判断一个数是否是质数:
方法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是质数。