用Python函数实现素数判断

素数是指只能被1和其本身整除的正整数，在数学中也称为质数。在计算机科学中，素数的重要性不言而喻，它们被广泛应用于密码学和数据加密等领域。

Python作为一种广泛使用的编程语言，在计算素数方面表现得十分出色，它提供了多种实现方式，以满足不同的需求。

以下将介绍3种Python实现素数判断的函数方法。

方法一：试除法

试除法是最常用的判断素数的方法之一，在Python中可以通过一个简单的函数来实现：

def is_prime1(num):
    if num <= 1:
        return False
    for i in range(2,num):
        if num % i == 0:
            return False
    return True

可以看到，该函数首先判断了特殊情况，即当输入的数字小于等于1时，直接返回False，表示该数字不是素数。

然后在循环中从2开始枚举到该数字前面的所有数字，若该数字能被其中的任何一个数字整除，即返回False，表示该数字不是素数。循环结束后，如果该数字能够整除除1和本身之外的其他数字，那么就返回True，表示该数字是素数。

该方法最简单直接，但是效率较低，对于大数的计算会十分费时。

方法二：优化试除法

试除法虽然简单直观，但效率不高。对于一个数n，若n不是素数，那么它必然是可以表示成某个质数p与另一个整数q的积。因此，我们可以只试除小于等于根号n的素数，若n不能被它们整除，则n是素数。这种方法被称为优化试除法，可以通过以下代码实现：

def is_prime2(num):
    if num <= 1:
        return False
    for i in range(2, int(num**(1/2))+1):
        if num % i == 0:
            return False
    return True

该函数与方法一类似，但在循环的范围上有所不同。在循环中，我们只需要枚举小于等于根号n的素数，就可以判断n是否为素数。这样可以避免重复的试除计算，提高了运行效率。

方法三：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种比较高效的求素数的方法，它利用了筛选法中的质数筛选策略，具体实现如下：

def is_prime3(num):
    if num <= 1:
        return False
    primes = [True]*(num+1)
    primes[0] = primes[1] = False
    for i in range(2, int(num**(1/2))+1):
        if primes[i]:
            for j in range(i*i, num+1, i):
                primes[j] = False
    return primes[num]

该函数首先创建了一个长度为num+1的布尔数组，初始所有数都标记为是素数，同时0和1都表示为非素数。

然后从小到大遍历素数列表，若该素数是素数，则将该素数的倍数标记为非素数。由于大于该素数的倍数已经被之前的素数筛选过，因此不需要再次遍历。

最后只需要判断输入的数字是否为素数。

结论

三种方法都可以判断素数，但在不同的应用场景下，存在显著的差异。

在时间和空间限制较小的情况下，可以使用简单的试除法或优化试除法实现素数判断。但是在计算大质数时，由于试除法的时间复杂度较高，需要耗费大量的时间和计算资源。

在此时，应该使用埃拉托斯特尼筛法，它的时间复杂度为O(nloglogn)，相对更高效。