pta浙大版python答案第三章 判断

题目链接：

https://pintia.cn/problem-sets/14/problems/779

一、题目大意

本题要求编写一个函数is_prime(n)，判断n是否为素数。若n是素数，则返回True；否则返回False。

二、算法思路

素数指只能被1和自身整除的大于1的正整数。

判断一个数n是否为素数，可以先遍历2到n-1之间的所有数i，若n能被某个i整除，则n不是素数。

但是这种方法的时间复杂度显然过高，不适用于大数判断。

另外一个更高效的算法是“质数筛选法”，即埃拉托斯特尼筛法（Sieve of Eratosthenes）。

该方法的基本思想是从2开始，将每个质数的倍数都标记成合数。一个数如果不是任何数的倍数，则它一定是素数。

步骤如下：

1.先把2作为素数，把2的倍数全部标记为合数。

2.找到下一个未标记的数3，把它作为素数，把3的倍数全部标记为合数。

3.找到下一个未标记的数5，把它作为素数，把5的倍数全部标记为合数。

4.重复步骤2、3直到需要判断的数N的平方根m，若该数为素数，则它没有被除过，即它保留的是初始的值2。

三、代码实现

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

本题中只需要实现is_prime函数即可。

is_prime函数首先判断n是否小于2，若是，则不是素数，直接返回False。然后遍历2到n平方根之间的所有数i，若n能被i整除，则n不是素数，返回False。若遍历完所有数都没有返回，则n是素数，返回True。

四、总结

本题考察了素数的判断算法，既可以使用暴力枚举的方式，也可以使用高效的质数筛选法。实现过程中需要注意程序的效率和算法的正确性。