博客

python怎么判断是否为质数

  • Post category:Python

下面是Python判断质数的完整攻略：

什么是质数

质数是指只能被1和本身整除的自然数，例如2、3、5、7、11、13、17等。

判断一个数是否为质数

判断一个数是否为质数可以采用以下两种方法。

  1. 枚举法

枚举法是一种简单、直接的判断质数的方法。枚举方法的思路是：对于一个正整数n，如果它不是1或者本身，那么它一定是由两个不同的自然数相乘得到的，即n = a * b (1 < a <= b < n)。那么，只需要枚举从2到n-1的所有自然数，判断n是否能够被它们整除即可。如果n不能被任何一个数整除，那么n就是质数。

下面是枚举法的代码实例：

def is_prime(num):
    """判断一个数是否为质数，返回True或False"""
    if num <= 1:
        return False  # 1不是质数
    for i in range(2, num):
        if num % i == 0:
            return False
    return True
  1. 根号法

根号法是一种更优化的判断质数的方法。它的基本思路是：对于一个正整数n，如果它不是1或者本身，那么它一定是由两个不同的自然数相乘得到的，即n = a * b (1 < a <= b < n)。那么，a和b中必有一个不大于根号n，另一个不小于根号n。因此，只需要枚举从2到根号n之间的所有自然数，判断n是否能够被它们整除即可。

下面是根号法的代码实例：

import math

def is_prime(num):
    """判断一个数是否为质数，返回True或False"""
    if num <= 1:
        return False  # 1不是质数
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

总结

以上就是Python判断质数的攻略了。两种方法各有优缺点，枚举法简单易懂，但对于大数会很耗时。根号法虽然更优化，但对于大数的质数检测还需进一步优化。在实际应用中，我们可以根据具体情况选择合适的方法来判断质数。

Tags: