python怎么判断是否为质数

判断一个数是否为质数的一种简单方法是试图将其除以小于它的每个整数。然而，这种算法的复杂度是O(n)，当n特别大时，速度会非常慢。因此，有一种称为埃拉托斯特尼筛法的优化算法，它可以在O(nlog(log(n)))的时间复杂度内判断一个数是否为质数。

以下是本文详细讲解python如何判断是否为质数的完整攻略：

常规方法

以下是一个通过求余运算判断一个数是否为质数的常规算法。假设我们要判断的数是n：

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

我们先判断n是否小于2，因为小于2的整数都不是质数。然后我们循环从2到n-1，每次都判断n除以这个数是否等于0。如果能被整除，说明n不是质数，返回False。否则，就是质数，返回True。

需要注意的是，这里的循环范围是2到n-1，因为1和n本身肯定都能被整除，没有必要循环到它们。

埃拉托斯特尼筛法

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种非常高效的判断质数的算法，它可以在O(nlog(log(n)))的时间复杂度内判断一个数是否为质数。以下是实现代码：

def sieve_of_eratosthenes(n):
    if n < 2:
        return []
    prime = [True] * (n + 1)
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return [i for i in range(2, n + 1) if prime[i]]

该算法先建立一个长度为n+1的布尔数组prime，其中所有的元素都被赋值为True。接下来从2开始循环，如果当前的数p是质数（即prime[p]为True），那么将2p、3p、4p、...全部标记为非质数。具体实现方法是将这些数在prime数组中的元素设为False。因为2p、3p、4p、...都可以分解为2、3、4、...和p的积，而p已经被确定是质数，因此这些积都不是质数。

对于任意一个小于等于n的数，如果它是质数，那么在上述过程中一定没有被标记为非质数。最终，prime数组中所有值不为False的下标就是小于等于n的所有质数。

以下是调用示例：

print(is_prime(3))  # True
print(is_prime(4))  # False
print(is_prime(5))  # True

print(sieve_of_eratosthenes(10))  # [2, 3, 5, 7]
print(sieve_of_eratosthenes(20))  # [2, 3, 5, 7, 11, 13, 17, 19]