卡迈克尔数是满足Korselt准则的合数：无平方因子，且对每个素因子p都有(p−1)∣(n−1)；需先排除素数、偶数及n
什么是卡迈克尔数？先看判定条件
卡迈克尔数不是素数，但满足费马小定理的“伪素性”：对所有与它互质的整数 a，都有 a^n ≡ a (mod n)。等价地，n 是合数，且对每个它的素因子 p，都有 (p − 1) | (n − 1)，同时 n 是无平方因子的（即不被任何素数的平方整除）。
这意味着判断不能只靠试除法测素性，必须验证三个条件：
-
n > 2且为合数（非素数、非 1） -
n是 square-free：分解后每个素因子指数均为 1 - 对每个素因子
p，(n - 1) % (p - 1) == 0
如何高效分解 n 并检查 square-free 性
暴力试除到 sqrt(n) 即可，不需要筛表或 Pollard-Rho。关键点在于：一旦发现某个素因子 p 满足 p*p 整除 n，立刻返回 false（违反 square-free）。
bool is_square_free(long long n) {
if (n <= 1) return true;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
n /= p;
if (n % p == 0) return false; // p² | original n
}
}
return true;
}注意：
立即学习“C++免费学习笔记（深入）”；
- 循环中要实时更新
n，否则会漏判残留大素因子 - 最后剩余的
n > 1是一个素因子（且只出现一次），不用再验平方 - 用
long long防止p*p溢出，尤其当n接近INT_MAX时
完整判定函数怎么写（含素性判断和因子遍历）
不能复用 is_prime 判定合数 —— 因为卡迈克尔数必须是合数，所以先排除素数；但更高效的做法是在分解过程中同步收集素因子，并顺便确认是否为合数（即至少找到一个因子）。
bool is_carmichael(long long n) {
if (n < 561) return false; // 最小卡迈克尔数是 561
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {
// 快速排除小因子合数（但需继续分解确认 square-free 和 p-1 条件）
}
<pre class="brush:php;toolbar:false;">vector<long long> factors;
long long temp = n;
for (long long p = 2; p * p <= temp; ++p) {
if (temp % p == 0) {
factors.push_back(p);
temp /= p;
if (temp % p == 0) return false; // not square-free
}
}
if (temp > 1) factors.push_back(temp);
if (factors.size() < 2) return false; // 至少两个不同素因子（卡迈克尔数必为奇合数，且 ≥ 3 个因子常见，但数学上只要 ≥ 2）
for (long long p : factors) {
if ((n - 1) % (p - 1) != 0) return false;
}
return true;}
容易踩的坑：
- 忘记检查
n是否为素数：若n是素数，即使满足(n−1)%(p−1)（此时只有自身一个因子），也不算卡迈克尔数 - 误把
1或4当作候选：它们不满足合数前提，直接排除 - 没处理
n分解后剩余的大素因子（即temp > 1的情况），导致漏因子、条件验证不全
实际使用时要注意数值范围和性能边界
卡迈克尔数很稀疏：前 10^6 内只有 43 个。所以对单次查询，O(√n) 分解完全可行；但若批量判断 10^5 个数，就该预筛小素数或缓存已知卡迈克尔数（如 561, 1105, 1729, 2465…）。
另外：
-
int类型只能安全处理到约 46340²，建议统一用long long - 标准库没有现成的
is_carmichael，别试图用std::pow+ 模运算模拟费马测试——那会溢出且慢，还无法 100% 判定（仅概率性） - 某些实现错误地认为“对几个
a满足a^n % n == a就是卡迈克尔数”，这是错的：必须对所有与n互质的a成立，而等价判定正是上面三条数论条件
真正要命的是漏掉 square-free 检查 —— 比如 1105 = 5 × 13 × 17，满足所有条件；但若误把 45 = 3² × 5 当作候选，虽然 (45−1)%(3−1)==0 且 (45−1)%(5−1)==0，却因含平方因子被排除。这个细节几乎所有人第一次写都会错。
