判断一个数是否是素数，是返回true, 不是返回false , 要求： 1）用自然语言设计算法， 2）计算算法的时间复杂度， 3）编程写判断素数的函数，并在主函数中读取键盘输入的整数，判断其是否为素数，打印输出判断的结果。

1）算法设计：

（1）输入一个正整数 $n$。

（2）从 $2$ 到 $\sqrt{n}$ 的所有整数中，判断 $n$ 是否能被整除，如果能，说明 $n$ 不是素数，返回 false。

（3）如果 $n$ 不能被 $2$ 到 $\sqrt{n}$ 中的任何一个整数整除，则说明 $n$ 是素数，返回 true。

2）算法时间复杂度：

该算法中，最耗时的操作是从 $2$ 到 $\sqrt{n}$ 的所有整数中判断是否能被 $n$ 整除，因此时间复杂度为 $O(\sqrt{n})$。

3）Python 代码实现：

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("{} 是素数".format(num))
else:
    print("{} 不是素数".format(num))

在上面的代码中，我们先定义了一个 `is_prime` 函数来判断一个数是否是素数。在主函数中，读取键盘输入的整数，调用 `is_prime` 函数进行判断，并打印输出结果。

相关问题

2.1 判断一个数是否是素数，是返回true, 不是返回false , 要求： 1） 用自然语言设计算法， 2） 计算算法的时间复杂度， 3） 编程写判断素数的函数，并在主函数中读取键盘输入的整数，判断其是否为素数，打印输出判断的结果。

1）算法设计：判断一个数是否是素数，可以采用试除法。从2到根号n枚举所有可能的因子，如果存在一个因子能够整除n，那么n就不是素数，否则n就是素数。

2）时间复杂度：该算法的时间复杂度为O(√n)，因为只需要枚举到根号n即可。

3）Python代码实现如下：

import math

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

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

在主函数中，我们通过input函数读取用户输入的整数n，然后调用is_prime函数判断n是否为素数，并根据判断结果打印输出相应的信息。

2.1 判断一个数是否是素数，是返回true, 不是返回false , 要求： 1）用自然语言设计算法， 2）计算算法的时间复杂度， 3）编程写判断素数的函数，并在主函数中读取键盘输入的整数，判断其是否为素数，打印输出判断的结果。

1）设计算法：判断一个数是否是素数，可以通过从2到该数的平方根之间的所有数进行除法运算，如果存在能够整除该数的数字，则该数不是素数，否则就是素数。

2）时间复杂度：该算法的时间复杂度为O(sqrt(n))，其中n是待判断的数字。

3）编程实现：

import math

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

if __name__ == "__main__":
    num = int(input("请输入一个整数："))
    if is_prime(num):
        print("{}是素数".format(num))
    else:
        print("{}不是素数".format(num))

在主函数中，首先读取键盘输入的整数，然后调用is_prime函数进行判断，最后根据判断结果打印输出。