Python 判断素数算法：原理、时间复杂度和代码实现

判断一个数是否是素数：算法原理、时间复杂度和代码实现

本文将带你深入了解如何判断一个数是否是素数，并提供完整的 Python 代码实现。

算法设计

判断一个数是否是素数，最常用的方法是从 2 到该数的平方根遍历每个数，判断该数是否能整除遍历到的数。如果存在能整除该数的数，则该数不是素数，否则是素数。

时间复杂度

该算法的时间复杂度为 O(√n)，其中 n 为待判断的数。这是因为我们只需要遍历到 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

num = int(input('请输入一个整数：'))
if is_prime(num):
    print(num, '是素数')
else:
    print(num, '不是素数')

测试样例

• 输入：7 输出：7 是素数

• 输入：10 输出：10 不是素数

• 输入：1 输出：1 不是素数（根据定义，素数是大于 1 的自然数）