卡迈克尔数是满足korselt准则的合数：无平方因子，且对每个质因数p都有(p−1)∣(n−1)；需先排除素数、偶数及小于2的数，再质因数分解并验证两条件。
什么是卡迈克尔数？先看判定条件
卡迈克尔数不是素数，但满足费马小定理的“伪素数”行为：对所有与它互质的整数 a，都有 a^n ≡ a (mod n)。等价地，对所有满足 1 且 <code>gcd(a, n) == 1 的 a，都有 pow_mod(a, n, n) == a。
但逐个验证所有 a 太慢。实用判定依赖Korselt准则：
一个合数 n 是卡迈克尔数 ⇔
-
n无平方因子（即每个质因数只出现一次） - 对
n的每个质因数p，都有(p - 1) | (n - 1)
所以核心是分解质因数 + 验证两个条件。
如何高效分解质因数并检查无平方性
对 n ≤ 10^9 级别的数，试除法足够快；更高量级需 Pollard-Rho，但日常判断卡迈克尔数极少需要。
关键点：
- 分解时一旦发现某个质因数
p满足p<em>p</em>p ≤ n且n % (p*p) == 0，可立即返回false（含平方因子） - 若
n被p整除后还剩一个 >1 的剩余数r，要检查r是否为质数（不能直接当质因数用，得确认） - 记录所有不同质因数到 vector，不要重复添加
示例片段（简化）：
vector<int> factors; int temp = n; for (int i = 2; i * i 1) factors.push_back(temp); // 剩余大质数 </int>
验证 (p−1) ∣ (n−1) 时的边界注意点
这个条件必须对每一个质因数 p 成立，缺一不可。常见疏漏：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 忘记检查
n是否为合数：若n是素数，直接排除（卡迈克尔数定义要求是合数） - 用
(n-1) % (p-1) == 0判断整除，但p == 2时p-1 == 1，永远成立——没问题，但别误以为可跳过 -
n很大时，n-1可能溢出 int？确保用 long long 做模运算或除法，尤其当n接近INT_MAX
验证循环：
for (int p : factors) {
if ((n - 1) % (p - 1) != 0) return false;
}
完整函数结构与典型错误输入
最终函数签名建议为 bool isCarmichael(long long n)，理由：
- 输入可能为
561、1105、1729这类经典卡迈克尔数，也可能是4（合数但含平方因子）、17（素数）、1或0（非合数，直接 false）
容易踩的坑：
- 不检查
n 或 <code>n == 2：这些都不是卡迈克尔数 - 把
1当作合数（它既不是素数也不是合数） - 对
n == 4，质因数是[2]，但4 % (2*2) == 0→ 含平方因子 → 正确返回 false - 卡迈克尔数必为奇数（因偶合数若满足 Korselt，则必含因数 2，要求
1 | (n-1)成立，但其他奇质因数p要求p-1为偶数且整除n-1，而n为偶 ⇒n-1为奇，无法被大于 2 的偶数整除），所以可提前if (n % 2 == 0 && n != 2) return n == 2 ? false : false;—— 实际上只需if (n % 2 == 0) return false;（除了 2 都不满足，而 2 是素数）
最简健壮入口：
if (n <p>卡迈克尔数稀疏且构造性强，实际中几乎不会遇到需要实时判断超大数的场景；但 Korselt 条件里的整除检查和质因数去重，是真正容易写错的地方。</p>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
