请用 Python 实现一个函数,接收一个整数序列,返回该序列中所有质数组成的列表。
考察说明
考查质数判断算法及 Python 基础实现能力
回答思路
- 【回答框架 1】定义质数为大于1且只能被1和自身整除的自然数。实现思路:遍历序列中的每个数,对每个数调用一个判断质数的辅助函数。
- 【回答框架 2】质数判断函数:若 n 小于等于1直接返回 False;从2到 sqrt(n) 取整检查是否能整除,若存在因子则非质数,否则为质数。
- 【回答框架 3】主函数:遍历输入序列,对每个元素调用 is_prime,将结果为 True 的元素收集到结果列表并返回。
- 【回答框架 4】边界情况:注意输入序列可能包含负数、0、1 或非整数类型,需提前处理或明确约定输入均为正整数。
- 【回答框架 5】复杂度:每个数判断质数的时间复杂度为 O(sqrt(n)),整体为 O(m*sqrt(k)),m 为序列长度,k 为最大数。对于大数可考虑预先生成质数表优化。
- 【关键点 1】用 n<=1 排除非质数
- 【关键点 2】只需检查到 sqrt(n) 即可减少循环
- 【关键点 3】注意遍历时的类型处理
- 【易错点 1】不要用 i 从2到 n-1 全遍历,效率低
- 【易错点 2】勿将1或0误判为质数
- 【易错点 3】对大整数直接判断可能超时,可考虑预筛法