卡迈克尔数是满足korselt准则的合数：n为奇合数、无平方因子，且对每个素因子p均有(p−1)∣(n−1)；需先排除素数和偶数，再质因数分解并验证三条件。
什么是卡迈克尔数？先看判定条件
卡迈克尔数不是素数，但满足费马小定理的“伪素性”：对所有与它互质的整数 a，都有 a^n ≡ a (mod n)。等价地，n 是合数，且对 n 的每个素因子 p，都有 (p−1) | (n−1)，同时 n 是无平方因子的（即不能被任何素数的平方整除）。
所以判断一个整数 n 是否为卡迈克尔数，必须同时满足三点：
-
n > 2且是合数（非素数、非 1） -
n是无平方因子数：对所有素因子p，p²不整除n - 对
n的每个素因子p，(n−1) % (p−1) == 0
如何高效分解 n 并提取素因子？
暴力试除即可，不需要 Pollard-Rho。因为卡迈克尔数增长极快（前几个是 561, 1105, 1729…），实际要判的 n 通常在 int 范围内（≤ 10⁹），试除到 sqrt(n) 完全可行。
关键点在于：必须完整分解出所有不同素因子，并验证无重复（即无平方因子）。
实操建议：
- 用
int i = 2开始循环，每次找到因子就除尽，并记录该因子一次 - 若最后剩余
r > 1，则r本身也是一个素因子 - 过程中一旦发现
n % (i*i) == 0，立刻返回 false（含平方因子） - 别忘了检查
n == 1或n是素数——这两种情况直接排除
示例片段（核心逻辑）：
vector<int> factors; int temp = n; for (int i = 2; i * i 1) factors.push_back(temp);</int>
为什么不能只用费马测试来判定？
单次费马测试（如选 a = 2）只能证伪：若 pow_mod(2, n, n) != 2，则 n 肯定不是卡迈克尔数；但若通过，无法确认它是卡迈克尔数——它可能是素数，也可能是其他基下的伪素数（比如 9 是合数，但 2⁹ ≡ 2 (mod 9)？不成立，但像 341 对 a=2 就通过了，却不是卡迈克尔数）。
卡迈克尔数的定义要求「对所有与 n 互质的 a 都成立」，穷举不可行。所以必须走数学结构判定路径：素因子分解 + 条件验证。
常见错误：
- 误把素数当成卡迈克尔数（漏判合数条件）
- 没检查无平方因子，把 1105（=5×13×17）错判为 121（=11²）→ 实际 121 不满足，但代码若没检测平方因子会出错
- 因子分解不全（比如漏掉大素因子），导致后续
(p−1)整除判断失效
边界和性能要注意什么？
int 范围内最大的卡迈克尔数是 101101（≈1e5），但你写的函数可能被传入任意 int，所以必须处理：
-
n ≤ 2→ 直接 false -
n是偶数且 ≠ 2 → 只有 2 是素数，其余偶合数一定含因子 2，而(2−1)=1总整除n−1，但还需检查其他因子；不过已知所有卡迈克尔数都是奇数，所以可提前if (n % 2 == 0) return n == 2 ? false : false; - 试除时用
i * i ，别写成 <code>i （浮点误差+慢） -
pow_mod在验证环节不需要——这里不用费马测试，只用整除判断
真正容易被忽略的是：卡迈克尔数至少有三个不同素因子（这是 Korselt 准则的推论）。所以如果分解后 factors.size() ，可直接返回 false。这个剪枝能快速拦截大量合数（如 15=3×5，只有两个因子，不可能是卡迈克尔数）。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
