博客

判断是否为质数即判断一个数是否只能被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列表推导式生成一个质数列表。

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