如何判断素数并输出指定范围内的素数?有哪些优化?
哪些公司问过
答案要点
- 基础试除:2 到 n-1,时间 O(n)
- 只需试除到 √n,用 i*i<=n 避免浮点误差,O(√n)
- 单独处理 2 后只试除奇数,次数减半
- 区间批量求素数用埃氏筛,从 i*i 开始标记倍数
- 100~200 之间共 21 个素数;0、1 和负数不是素数
易错点
- 把 1 当成素数
- 用 sqrt 浮点结果做循环边界,存在精度问题
- 筛法从 2*i 开始标记,虽然正确但做了多余工作
面试官常见追问
- 埃氏筛和线性筛有什么区别?
- 100 以内有多少个素数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。