博客

判断一个数字是否为质数是一个经典的算法问题，Python作为一门优秀的编程语言，也提供了多种方法来解决这个问题。接下来，我将为大家介绍Python中常用的几种方法来判断一个数字是否为质数。

什么是质数

质数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除的数。

方法一：枚举法

枚举法是最基础的一种方法，我们可以依次枚举2到n-1的所有数来判断该数是否为质数。

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，因为因子大于n的数无法整除它；然后从2开始枚举到n-1，每次判断n是否能够整除i，如果能整除，则n不是质数，返回False；否则n是质数，返回True。

方法二：改进枚举法

枚举法的时间复杂度是O(n)，可能对于较大的数运行时间较长，因此我们可以对其进行一些改进。

def is_prime(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i+2) == 0:
            return False
        i += 6
    return True

在这里，我们首先考虑特殊情况：如果n小于2，则返回False；如果n等于2或者3，则返回True。接着，我们判断n是否为2或3的倍数，如果是，则n不是质数，返回False。

在上述情况下，如果n不是2或3的倍数，那么它一定是6的倍数加或减1，因此我们只需要枚举6i+1和6i-1的情况即可，而且，我们不需要判断i是否为奇数或偶数，因为每次i都增加6，只有两种情况，即i为奇数或者偶数。