输出小于 n 的所有质数(筛法)
哪些公司问过
vivo1模捷作1
答案要点
- 质数定义:大于 1 且只能被 1 和自身整除
- 试除法只需检查到平方根,整体约 O(n√n)
- 埃氏筛从 i 乘 i 开始标记倍数,复杂度 O(n log log n)
- 线性筛让每个合数只被最小质因子标记一次,复杂度 O(n)
- 边界:n 小于等于 2 无质数,注意 i 乘 i 溢出;100 以内共 25 个质数
易错点
- 把 1 当成质数
- 外层循环条件写成 i 小于 n 的平方根时取整出错,漏掉边界
- 题目要求小于 n 却把 n 本身也算进去
面试官常见追问
- 为什么从 i 乘 i 开始标记?
- n 非常大内存不够怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。