GESP 五级 · GESP 202412 C++ 五级 第 18 题

任何一个大于 $1$ 的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。

质数判定优化：只需检查2到√n。偶数除了2都不是质数。判断素数的时间复杂度O(√n)。

1不是质数也不是合数。埃氏筛法标记时从i×i开始而非从2×i开始，因为小于i×i的倍数已经被更小的质数筛过。

【考点】质因数分解｜算术基本定理｜唯一分解条件

1. 🎯 考纲定位

GESP 五级"算法基础"模块，核心是质因数分解与算术基本定理。命题人专卡"唯一分解"在"不同质数"前提下的真假判定，这是五级学生最容易混淆的定理细节——背过"分解唯一"却忽略"互不相同"这一关键限定。