Python判断素数算法：实现、时间复杂度及示例

Python 判断素数算法：实现、时间复杂度及示例

判断一个数是否为素数是常见的算法问题。本文将详细介绍如何使用试除法来判断一个数是否为素数，并分析其时间复杂度，最后给出 Python 代码实现及示例输出。

1. 设计算法：

判断一个数是否为素数，可以采用试除法，即从 2 到 sqrt(n) 逐一判断 n 能否被整除。如果 n 能被 2 到 sqrt(n) 之间的任意一个数整除，则 n 不是素数，反之则是素数。

2. 时间复杂度：

在试除法中，需要依次判断 2 到 sqrt(n) 之间的数，因此时间复杂度为 O(sqrt(n))。

3. 编程实现：

import math

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

n = int(input('请输入一个整数: '))
if is_prime(n):
    print('{}是素数'.format(n))
else:
    print('{}不是素数'.format(n))

4. 示例输出：

请输入一个整数: 17
17是素数

请输入一个整数: 20
20不是素数

总结：

本文介绍了判断一个数是否为素数的算法，并使用 Python 代码实现了该算法。通过学习本文，读者可以了解到试除法的原理、时间复杂度分析以及 Python 代码实现方法，并能够应用该算法解决相关问题。