卡迈克尔数是满足Korselt准则的合数：无平方因子，且对每个素因子p都有(p−1)∣(n−1)；需先排除素数、偶数及n<561，再质因数分解并验证两条件。
什么是卡迈克尔数？先看判别条件
卡迈克尔数是合数 n，且对所有与 n 互质的整数 a，都满足 a^(n−1) ≡ 1 (mod n)。但直接枚举所有 a 显然不可行。实际判别用的是等价的**Korselt 准则**：
一个合数 n 是卡迈克尔数 ⇔ 对 n 的每个素因子 p，都有 (p − 1) | (n − 1)，且 n 是无平方因子的（即每个素因子只出现一次）。
如何分解质因数并验证 Korselt 条件
核心步骤是：先试除得到所有不同质因子，同时检查是否含平方因子；再对每个质因子 p 检查 (n − 1) % (p − 1) == 0。注意：
- n 必须是合数（不能是质数，也不能是 1）
- 质因数分解只需到 sqrt(n) 即可
- 若最后剩余的 n > 1，它本身是一个质因子（且指数为 1，否则已含平方因子）
常见错误现象：
- 忘记检查 n 是否为合数，导致质数被误判（如 7 满足 Korselt 但不是卡迈克尔数）
- 未验证无平方性，把 12 = 2²×3 当作候选（其实 2² 已违反条件）
- 对大数（如 n > 1e9）暴力试除太慢，但卡迈克尔数本身稀疏，实际测试中 n 就够覆盖前几十个
示例逻辑片段：
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
bool isCarmichael(int n) {
if (n < 2 || isPrime(n)) return false; // 排除质数和边界
int temp = n;
for (int p = 2; p * p <= temp; p++) {
if (temp % p == 0) {
int cnt = 0;
while (temp % p == 0) {
temp /= p;
cnt++;
}
if (cnt > 1) return false; // 含平方因子
if ((n - 1) % (p - 1) != 0) return false;
}
}
if (temp > 1) { // 剩余大质因子
if ((n - 1) % (temp - 1) != 0) return false;
}
return true;
}
isPrime 怎么写才不拖慢整体判断
卡迈克尔数最小是 561，所以 n 通常不小，但 isPrime 只需用于初步过滤——若 n 是质数，直接返回 false。这里不需要 Miller-Rabin，普通试除即可，但要注意优化：
- 只需检查到 sqrt(n)
- 先特判 2，再只试奇数
- 对小 n（如 ）可直接查表或硬编码
容易踩的坑：
- 把 sqrt(n) 写成 sqrt(n)+1 导致浮点误差（建议用 i * i ）<br>- 忘记 <code>n == 2 时返回 true，结果 2 被误判为合数，进而影响后续逻辑
- 在 isCarmichael 中重复调用 isPrime 和质因数分解，其实两者可合并：分解过程中若发现只有一个因子且等于 n，说明 n 是质数
几个典型测试用例与边界行为
验证实现是否靠谱，得盯住这几个关键值：
- 561：最小卡迈克尔数（3×11×17），必须返回 true
- 4：合数但含平方因子（2²），应返回 false
- 17：质数，应返回 false
- 1 或 0：非正整数，按定义不属于卡迈克尔数，返回 false
- 1105：第二个卡迈克尔数（5×13×17），(1105−1)=1104 能被 4、12、16 整除，应返回 true
性能提示：
- 卡迈克尔数极稀疏（1e6 内仅 43 个），所以即使对每个输入都做完整分解，也不会卡顿
- 但若批量判断大量数，可预处理出 1e6 内所有卡迈克尔数打表，查表 O(1)
最易被忽略的一点：Korselt 准则要求 n 是**无平方因子合数**，这两个条件缺一不可。很多人只检查整除性，忘了先确认“合数”和“无平方”，导致 1、质数、或像 8 这样的数被错误归类。
