PTA 基础181 关于素数筛法的思考

相关链接 PTA 181 求因子和 C++格式化输出 微秒级计时 素数筛算法 因子和公式 直接上结论 直接使用 Sqrt(n) 为循环上限的方法,时间稳定O(sqrt(n)),程序运行不会超时 素数筛法理论复杂度小于O(sqrt(n)),在因子远小于n的情况下能达到最佳效果 由于算法相对复杂,素数筛法的运行时间会更高 在大数区间 [108,109] 内随机选取的平均运算时间是 素数筛: 开方法 ≈ 2: 1 部分运行结果可见下图,前4个数为比较有代表性的测试数字,最后为4中的平均时间 主要思路 首先可以确定本题直接使用以开方为上限的循环足以在规定时间内完成题目,于是考虑是否可以