Python 判断一个数是否为质数

在本文中，我们将介绍如何使用Python编程语言来判断一个数是否为质数。质数是只能被1和自身整除的正整数，不包括1。例如，2、3、5、7、11都是质数，而4、6、8、9等则不是。

方法一：暴力法

最简单的方法是使用暴力法。我们可以从2开始，逐个尝试用该数去除待判断的数。如果存在可以整除的数，则该数不是质数。下面是使用暴力法判断一个数是否为质数的代码示例：

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

num = 17
if is_prime(num):
    print(num, "是质数")
else:
    print(num, "不是质数")

在上述代码中，我们定义了一个is_prime函数，该函数接受一个参数n，判断n是否为质数。我们首先判断如果n小于等于1，则直接返回False。然后使用循环从2到n-1尝试将n除以每个数i。如果存在可以整除的数，则说明n不是质数，返回False。如果循环结束仍然没有找到可以整除的数，则说明n是质数，返回True。

运行上述代码，输出结果为：

17 是质数

方法二：优化的暴力法

在上述代码中，我们从2一直遍历到n-1，但实际上只需要遍历到n的平方根即可。因为如果一个数可以被大于其平方根的数整除，那么一定也可以被小于其平方根的数整除。我们可以利用这个性质来优化代码，减少不必要的计算。

下面是使用优化的暴力法判断一个数是否为质数的代码示例：

import math

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

num = 17
if is_prime(num):
    print(num, "是质数")
else:
    print(num, "不是质数")

在上述代码中，我们使用了math模块的isqrt函数来计算n的平方根，并将其转换为整数。然后我们使用优化后的循环条件range(2, math.isqrt(n) + 1)，只遍历到n的平方根。

运行上述代码，输出结果与之前的方法一相同：

17 是质数

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

埃拉托斯特尼筛法是一种高效的质数判断算法，可以快速筛选出一定范围内的所有质数。该算法的基本思想是从2开始，将每个质数的倍数标记为合数，直到遍历完所有小于等于待判断数的数。

下面是使用埃拉托斯特尼筛法判断一个数是否为质数的代码示例：

def is_prime(n):
    if n <= 1:
        return False

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1

    return is_prime[n]

num = 17
if is_prime(num):
    print(num, "是质数")
else:
    print(num, "不是质数")