如何编写Python函数来判断一个数是否为素数？

素数是指只能被 1 和其本身整除的数。判断一个数是否为素数是程序设计中经典的问题之一，本文将介绍如何编写Python函数来判断一个数是否为素数。

判断一个数是否为素数，最直接的方法就是从 2 到该数的平方根之间的所有数依次进行整除运算，如果存在能整除的数，则该数不是素数，否则是素数。不过这种方法的时间复杂度为 O(n) ，当数据量比较大时，效率就变得非常低下。

为了优化判断素数的时间复杂度，我们可以使用质数的判定方法，也就是所谓的 ” 厄拉多塞筛法 ” 对这个数的因子试除减少，使得时间复杂度降低到 O( n^(1/2) )。其思路如下：

（1）先准备一个数组来存储2到n-1的所有数；

（2）从2开始遍历数组，标记所有2的倍数，即2,4,6,...的位置都标记为1；

（3）再从3开始遍历数组，标记所有3的倍数，即3,6,9,...的位置都标记为1；

（4）以此类推，从遍历到 sqrt(n) ，因为在sqrt(n)之后的数如果是n的因子，那么一定在sqrt(n)之前的范围内已经标记过了；

（5）统计所有在数组中标记为0的数，如果其个数为1，那么n就是素数。

下面是代码实现：

import math

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

num = int(input("Please enter a positive integer: "))
if is_prime(num):
    print(num, "is a prime number.")
else:
    print(num, "is not a prime number.")

上述代码中的 is_prime() 函数接收一个参数 num ，用于判断 num 是否为素数。首先需要判断 num 是否小于等于 1 ，如果是，该数不是素数，直接返回 False ；如果 num 等于 2 ，返回 True ；如果 num 是偶数，返回 False ；否则，从 3 开始遍历到 sqrt(num) ，步长为 2 ，判断 num 是否可以被 i 整除。如果能整除，返回 False ；否则，返回 True 。

在主函数中，通过调用 is_prime() 函数来判断输入的正整数是不是素数。如果是素数，输出“num is a prime number.”，否则输出“num is not a prime number.”。

需要注意的是，在计算 sqrt(num) 时，需要使用 math.sqrt() 函数取整，使得 sqrt_num 是整数。此外，在遍历时，需要跳过偶数，即步长为 2 。

总的来说，使用厄拉多塞筛法判断素数的时间复杂度为 O( n^(1/2) ) ，比直接遍历的 O(n) 要快得多，是一个效率更高的算法。