素数判断代码实现疑问：两种方案可行性及时间复杂度差异咨询

问题1：第二种素数筛选实现的可行性 #

• 仅在筛选范围上限 n ≤ 121（也就是11的平方）时可行，超出这个范围就会输出错误结果。
• 背后的逻辑依据：如果一个正整数是合数，那么它一定存在至少一个不大于其平方根的质因数。你预先存入的素数最大是7，对应能覆盖的合数判断上限是7的下一个素数11的平方=121，只要数字小于121，所有合数的质因数都不会超过7，过滤掉能被2、3、5、7整除的数之后剩下的就都是素数。
• 超出范围的错误示例：当n设置为130时，121是11的平方，不能被2、3、5、7整除，会被你的代码误判为素数加入结果数组，最终输出错误。
• 你当前的代码还有一处小瑕疵：遍历从i=2开始，其实2、3、5、7本身会被过滤条件排除，不会重复加入数组，但如果要适配更小的n（比如n=5），你预先存入的数组已经包含了小于n的素数，不会出问题，只是有冗余的判断。

问题2：两种实现的时间复杂度差异 #

两者时间复杂度差距非常大：

• 第一种checkPrime是单个数的素数校验函数，原生实现的时间复杂度是O(n)，如果用它来筛选1到n的所有素数，总时间复杂度是O(n²)，而且你写的版本没有做提前终止（找到因数后没有break，仍然会继续循环到i<n），实际运行速度会更慢。
• 第二种实现固定做4次取模判断，遍历范围是1到n，总时间复杂度是O(n)，在适用范围内运行速度远快于第一种实现。如果把你的思路扩展为通用素数筛（动态把新找到的素数加入判断列表，代替固定的2、3、5、7），最终就是时间复杂度为O(n log log n)的埃拉托斯特尼筛法，性能仍然远优于第一种逐个校验的实现。

内容的提问来源于stack exchange，提问作者Random Stuff