面试题库 › 嵌入式 › 输出小于 n 的所有质数(筛法)

输出小于 n 的所有质数(筛法)

难度 ★☆☆在 2 场真实面经中被问到 方向:嵌入式考点:数学与智力题

哪些公司问过

vivo1模捷作1

常见岗位:Java 后端、嵌入式软件

答案要点

  1. 质数定义:大于 1 且只能被 1 和自身整除
  2. 试除法只需检查到平方根,整体约 O(n√n)
  3. 埃氏筛从 i 乘 i 开始标记倍数,复杂度 O(n log log n)
  4. 线性筛让每个合数只被最小质因子标记一次,复杂度 O(n)
  5. 边界:n 小于等于 2 无质数,注意 i 乘 i 溢出;100 以内共 25 个质数

易错点

面试官常见追问

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

相关面试题