GESP 五级 · GESP 202603 C++ 五级 第 21 题

根据唯一分解定理，如果大于 $1$ 的整数不能被任何不超其平方根的质数整除，那么 $n$ 必定是质数。

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

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

【考点】质因数分解｜质数判定｜唯一分解定理

1. 🎯 考纲定位

五级《数论与密码学基础》模块核心命题。这道题卡住的是90%选手对「质数判定」原理的模糊认知——他们知道「试除到平方根」是做法，却说不清「为什么到平方根就足够」，命题人就是针对这个认知断层设的验证题。