卡迈克尔数是满足费马小定理伪素性条件的合数n，即对所有与n互质的a均有a^(n−1)≡1(mod n)，其充要条件为：n无平方因子、至少含3个不同奇素因子，且每个素因子p满足(p−1)∣(n−1)。
什么是卡迈克尔数？先确认你真要判这个
卡迈克尔数是合数 n，满足对所有与 n 互质的整数 a，都有 a^(n-1) % n == 1。它长得像素数（通过费马小定理检验），但实际不是——常被用作 RSA 或素性测试里的反例。
注意：你大概率不需要从头实现完整判定。真正需要时，通常是因为在实现 Miller-Rabin、写密码学练习题，或调试某个“误把卡迈克尔数当素数”的 bug。盲目套公式会掉进性能和精度坑里。
直接暴力验证？别试——先筛出合数再分解质因数
暴力枚举所有 a ∈ [2, n-1] 并检查 powmod(a, n-1, n) 是否恒为 1，时间复杂度是 O(n log n)，n > 10^4 就卡死。卡迈克尔数本身稀疏（前 10 亿内仅约 2000 个），所以更靠谱的路径是：先快速排除素数，再验证结构特征。
- 用
is_prime(n)先筛掉素数（哪怕只用试除到sqrt(n)）——素数不可能是卡迈克尔数 - 若
n是合数，对其做质因数分解（n = p1^e1 * p2^e2 * ... * pk^ek） - 卡迈克尔数必须满足三个条件：
– 所有pi互不相同（即无平方因子，ei == 1）
– 每个pi - 1整除n - 1
– 至少含 3 个不同质因子（k >= 3）
例如 561 = 3 × 11 × 17：3−1=2、11−1=10、17−1=16，都整除 560，且无平方因子、三因子 → 是卡迈克尔数。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
如何安全算 a^(n-1) % n？用快速幂 + long long 防溢出
即使只验证单个 a（比如做反例测试），也要防中间结果溢出。C++ 标准库没内置模幂，得手写：
long long powmod(long long a, long long b, long long mod) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = (__int128)res * a % mod; // __int128 防乘法溢出（gcc）
a = (__int128)a * a % mod;
b >>= 1;
}
return res;
}关键点：
– 必须用 __int128（或自己写大数乘法）处理 a * a，否则 mod 接近 2^31 时就溢出
– 不要用 int 或 long 存中间值，long long 仅保底，乘法仍需扩展
– 如果编译器不支持 __int128（如 MSVC），得改用二分乘法（mulmod）
常见误判场景：边界值、小合数、类型混用
实测中容易栽在这些地方：
-
n = 1、n = 2、n = 4：它们都不是卡迈克尔数（1非合数，2是素数，4 = 2²有平方因子） -
n = 561、1105、1729是最小的几个，可当单元测试用例 - 写
for (int a = 2; a 却没加 <code>gcd(a, n) == 1判断——卡迈克尔定义只约束互质的a，非互质时a^(n-1) % n可能为 0 或其他值，不能拿来证伪 - 用
int当参数传入powmod，而n是1e9级，导致隐式转换丢失精度
真正可靠的判定函数，核心逻辑只有三步：合数判断 → 质因数分解 → 检查每个 p_i - 1 | n - 1。其余都是围绕这三步填坑。分解质因数本身已是瓶颈，别指望在线性时间内搞定大数。
