面试题库 › 游戏开发 › 如何判断素数并输出指定范围内的素数?有哪些优化?

如何判断素数并输出指定范围内的素数?有哪些优化?

难度 ★☆☆在 5 场真实面经中被问到 方向:游戏开发考点:数学与智力题

哪些公司问过

vivo2百度1联发科1吉比特1

常见岗位:嵌入式软件、C/C++ 软件开发、游戏服务端

答案要点

  1. 基础试除:2 到 n-1,时间 O(n)
  2. 只需试除到 √n,用 i*i<=n 避免浮点误差,O(√n)
  3. 单独处理 2 后只试除奇数,次数减半
  4. 区间批量求素数用埃氏筛,从 i*i 开始标记倍数
  5. 100~200 之间共 21 个素数;0、1 和负数不是素数

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题