100的因数有7个，但面试官只关心你能不能写出第8个判断条件。这不是数学题，是效率意识的试金石。
去年某大厂算法岗终面，候选人简历光鲜，却在手写素数判断时栽了跟头。面试官后来复盘：「不是不会，是从没想过循环边界能少跑一半。」素数检测这7行代码，藏着两个让资深工程师翻车的细节。
因数检测：为什么100的因数只有7个，不是8个？
先看基础款。检测100的因数，代码逻辑直白得像超市收银：从2开始试除，能整除就打印，除数自增直到等于被除数。
Python版本跑出来的结果：2、4、5、10、20、25、50。数一下，7个。
但100的因数明明有1、2、4、5、10、20、25、50、100，共9个。代码只输出7个，因为循环条件是div < num，主动排除了1和100本身。
这个设计很产品经理思维——排除 trivial cases（平凡情况），只关注「非平凡因数」。就像用户画像过滤掉极端值，代码也在过滤无意义的边界。
Java和JavaScript版本逻辑完全一致，连变量命名都没换。这种跨语言的保守设计，说明算法层的东西，语法糖改变不了骨架。
素数判断：那个让循环少跑50%的符号
素数定义简单：只能被1和自身整除。但代码实现里有个反直觉的优化。
常规思路是从2试除到n-1。但原文代码写的是div <= no // 2，双斜杠是整除，意思是「试到一半就停」。
为什么够用了？假设n有个因数d大于n/2，那对应的配对因数n/d必然小于2。小于2的正整数只有1，而1不算「非平凡因数」。换句话说，大于n/2的因数，除了n本身，不存在。
这个优化把时间复杂度从O(n)砍到O(n/2)。在大厂面试里，写出这个边界的人，和写div < no的人，会被分到不同的评级池。
flag变量的设计也很老派。Python用布尔，Java用boolean，都是先假设「是素数」，一旦发现因数就翻转。这种「无罪推定」的逻辑，比直接return更符合早期编程教育的审美——单入口单出口，flag统一管控流程。
从教学代码到生产环境：还差几步？
原文代码是标准教材写法，但投到生产环境会被打回。
第一，输入没做校验。int(input())在Python里遇到字符串直接崩溃，Java的Scanner倒是类型安全，但负数、0、1的边界都没处理。1不是素数，这段代码会误判。
第二，复杂度还能再砍。试除到√n就够了，原理和「试到一半」类似：如果n=a×b，a和b至少有一个不大于√n。这个优化能把O(n)降到O(√n)，面试写出来是加分项。
第三，空间换时间的工业解法。埃拉托斯特尼筛法预处理，查询变O(1)。但筛法代码量翻倍，教学场景不会首选。
原文的定位很清晰：不是最优解，是可理解的解。就像产品经理画原型，先保逻辑通顺，再抠交互细节。
为什么大厂爱考这题？
素数检测是算法面试的「瑞士军刀题」。考察点分层：
基础层：能不能写出无bug的循环。很多人死在边界条件，<和<=搞混，或者忘记自增死循环。
进阶层：知不知道优化到n/2。这题筛的是「有没有主动思考过效率」的人。
拔尖层：能不能推到√n，甚至说出筛法。到这一层，面试官开始聊项目深度了。
某头部云厂商的校招数据：算法题通过率约35%，但素数相关变体题的区分度最高——会的人分都高，不会的人理由各异。
代码风格也在考察范围内。原文三版代码，Python用蛇形命名（num_div），Java用驼峰（numDiv），虽然示例里没体现，但变量命名的一致性，是工程素养的暗线指标。
最后留个思考题：如果输入是10^12级别的数，这段代码需要跑多久？√n优化后呢？筛法预处理10^6以内的素数再查询呢？三种策略的 trade-off（权衡），对应三种不同的系统架构思维。
热门跟贴