GESP 五级 · GESP 202312 C++ 五级 第 20 题

小杨设计了一个拆数程序，它能够将任意的非质数自然数 $N$ 转换成若干个质数的乘积，这个程序是可以设计出来的。

这题其实就考一个核心认知：任何合数（非质数）都能被拆成质数的乘积。拿到题别想复杂算法，直接回忆质数与合数的定义和欧几里得定理的推论，就能秒懂为什么程序一定能设计出来。

最容易掉进两个坑：一是把'非质数'理解成'所有自然数'，忽略了质数本身无法再拆，导致纠结于是否存在反例；二是死磕实现细节，比如纠结用埃氏筛还是试除法，完全跑偏。这道题是纯概念判断，不需要写代码，只要抓住'合数必有质因子'这个数论基石，就能稳稳选对。

【考点】质数与合数的定义、欧几里得定理的推论（合数必有质因子）、审题细节。

GESP五级这道题，命题人其实是在考大家是否真正理解了'质数'和'合数'在数论里的根本区别，以及'任意非质数都能拆成质数乘积'这个经典结论。很多人能背下'质数只有1和它本身两个约数'，但一旦遇到'拆数程序'这种应用场景，就会卡壳：'那合数怎么拆？是不是有无限种拆法？会不会遇到拆不掉的数？'

命题人的挖坑点非常隐蔽：题目特意强调了'非质数'。如果改成'任意自然数'，那答案立马变错，因为质数本身是无法再拆成更小的质数乘积的（除非允许拆成1，但1不是质数）。所以，审题不细的同学，看到'程序可以设计出来'就慌了，心想'万一遇到质数怎么办？'从而怀疑整个命题。但仔细看，'非质数'这个限定词已经帮我们要排除了质数这个反例，剩下的全是合数。

思考心法很简单：拿到题先问自己，'合数有什么性质？' 根据欧几里得定理的推论，任何一个大于1的合数N，必然存在一个质因子p，且p ≤ √N。这意味着，我们只要从2开始试除，最多试到√N，一定能找到一个能整除N的数d。d可能是质数，也可能是合数，但如果是合数，它里面还藏着更小的质因子，我们可以继续拆d，直到所有因子都是质数为止。这个过程是确定性的，不会死循环，也不会遇到拆不掉的数。

具体怎么算呢？虽然这道题不需要写代码，但理解流程有助于确认'程序可设计性'： 1. 输入N（已知N是非质数，即N是合数且N>1）。 2. 从i=2开始遍历到√N。 3. 一旦找到i能整除N，就把i记录下来，然后让N = N / i，继续循环（因为新的N可能还是合数，需要继续拆）。 4. 直到N变成1，所有记录的因子就是质因子。

这里有个易错点要特别提醒：很多人会纠结'如果i本身是合数怎么办？'比如N=12，i=2时整除，记录2，N变成6；i=3时整除，记录3，N变成2；i=2时（因为√2≈1.4，循环结束？不对，这里要注意循环范围）。其实只要保证遍历到√N，且每次除尽后重新计算新的√N，逻辑就严密了。更严谨的做法是，每次找到因子d后，把d加入结果集，然后令N=N/d，继续从d开始（或从2开始）检查，直到N=1。这样无论d是质是合，最终结果集里全是质数。

再回头看命题视角：命题人故意不让你写程序，而是考你对数论结论的把握。'程序可以设计出来'等价于'存在一种算法能将任意合数分解为质数乘积'，这在数学上是绝对成立的。所以选项A'正确'是铁板钉钉的。

考频与趋势：从题库数据看，'质数与合数'是高频考点，共考过52题，覆盖7个级别。其中2024年考了21题、2025年13题、2023年7题，说明近三年来命题人特别偏爱考数论基础概念，尤其是结合简单算法场景的判断题。GESP五级考了29题，占比过半，说明这个级别非常重视数论直觉。

预测：基于2024-2025年的爆发式考频，未来GESP五级、六级甚至七级，仍大概率会考'质数/合数判定'或'分解质因数'的概念辨析题，形式可能包括'判断某算法是否能处理所有输入'、'找出反例'等。暂无足够依据预测具体年份，但趋势明确：数论基础是GESP五级的'必考点'，复习时一定要把定义、定理和简单算法流程吃透，别只背结论。