python怎么判断是否为质数

  • Post category:Python

判断是否为质数即判断一个数是否只能被1和它本身整除。下面是Python的两种常见方法来判断一个数字是不是质数的攻略:

方法一:试除法

算法思路

从2开始试除至比该数的平方根小的所有整数,如果能被整除,则该数不是质数。

代码实现

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

其中,range()函数取值范围为[2, sqrt(n)],使用int()函数向下取整,加1是为了确保range()函数不会取到比n的平方根略大的小数。

方法二:筛选法

算法思路

从小到大枚举每个数字x,如果该数字没有被筛掉,则它一定是质数。然后筛掉x及x的2倍、3倍、4倍……(不大于n)。

代码实现

def sieve(n):
    if n < 2:
        return []
    prime_list = [True] * (n+1) 
    prime_list[0] = prime_list[1] = False # 0, 1不是质数
    for i in range(2, int(n**0.5)+1):
        if prime_list[i]:
            prime_list[i*i: n+1: i] = [False] * len(prime_list[i*i: n+1: i]) 
    return [i for i in range(n+1) if prime_list[i]]

其中,prime_list是一个数组用来记录每个数字是否为质数。初始时,prime_list[0]和prime_list[1]都被设为False。从小到大枚举每个数字x,如果该数字没有被筛掉,则它一定是质数。 然后,我们就可以将x的倍数标记为非质数(即prime_list的值为False)。我使用了Python的高级语法技巧来实现这一点。最后,利用python列表推导式生成一个质数列表。

总的来说,这两种判断质数的方法各有优缺点,应根据实际需求来选择使用哪一种。