python判断所输入的任意一个正整数是否为素数的两种方法

确切判断一个数是否为素数一直是程序设计中的一个经典问题。接下来我们将介绍两种使用python实现判断正整数是否为素数的方法。

方法一：暴力枚举法

所谓暴力枚举法，即遍历2到n-1之间的所有自然数，如果n能被其中任何一个数整除，则n就不是素数。该方法的实现代码如下：

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

代码中首先判断输入的数是否小于2，因为从2开始才有素数的概念，如果小于2直接返回False。接着用for循环遍历2到n-1之间的所有自然数，依次判断n能否被其中某个数整除，如果整除则返回False，说明n不是素数。如果for循环结束时仍然没有判断出n不是素数，则返回True，说明n是素数。

接下来让我们试一下使用该方法来判断100和101是否为素数：

print(is_prime(100)) # False
print(is_prime(101)) # True

运行输出结果：

False
True

结果表明了暴力枚举法可以非常准确地判断一个正整数是否为素数。

方法二：试除法

方法一虽然准确，但是效率非常低，时间复杂度为O(n)，当输入的数非常大时，运算时间会非常长。而试除法是一种更加高效的判断正整数是否为素数的方法。该方法判断一个数是否为素数的原理和暴力枚举法一样，只不过试除法判断的范围不是2到n-1，而是2到n的平方根。因为如果一个数能被大于它平方根的数整除，那么小于它平方根的数就会同样能够整除。该方法的实现代码如下：

import math

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

代码中首先判断输入的数是否小于2，因为从2开始才有素数的概念，如果小于2直接返回False。接着用for循环遍历2到n的平方根之间的所有自然数，依次判断n能否被其中某个数整除，如果整除则返回False，说明n不是素数。如果for循环结束时仍然没有判断出n不是素数，则返回True，说明n是素数。在代码中使用了math模块中的sqrt函数来计算n的平方根。

接下来让我们试一下使用该方法来判断100000007和100000019是否为素数：

print(is_prime(100000007)) # True
print(is_prime(100000019)) # True

运行输出结果：

True
True

结果表明了试除法可以非常准确地判断一个正整数是否为素数，在效率上也要远好于暴力枚举法。

以上是两种使用python实现判断正整数是否为素数的方法和使用示例。需要注意的是，如果要判断大量位数比较大的数是否为素数，还需要使用更加优化的算法，否则运算时间将会非常长。希望本文能够帮助到大家。