卡迈克尔数是满足Korselt准则的合数：无平方因子，且对每个质因数p都有(p−1)∣(n−1)；需先排除素数、偶数及n
什么是卡迈克尔数？先确认你真要判它
卡迈克尔数是合数 n，满足对所有与 n 互质的整数 a，都有 a^(n-1) ≡ 1 (mod n)。它长得像素数（通过费马小定理检验），但其实不是——所以常被用于测试素性算法的鲁棒性。别一上来就写判定逻辑：先确保 n > 2 且是合数，否则直接返回 false。很多实现漏掉“必须是合数”这一前提，导致把素数也误判为卡迈克尔数。
怎么快速验证“对所有互质 a 都成立”？别真遍历
暴力枚举所有 a ∈ [2, n-1] 并检查同余太慢（O(n log n)），而且没必要。Korselt 准则才是实用判断依据：n 是卡迈克尔数 ⇔ n 是无平方因子的合数，且对 n 的每个素因子 p，都有 (p−1) | (n−1)。这意味着你只需做三件事：
- 用试除法或预筛分解
n，得到全部不同素因子（注意：若某素因子平方整除n，如12 = 2²×3，直接false） - 对每个素因子
p，检查(n - 1) % (p - 1) == 0 - 确保至少有两个不同素因子（卡迈克尔数必为奇合数，最小的是
561 = 3×11×17）
写代码时最容易错的三个地方
实际编码中，这几个点几乎必踩坑：
-
n小于561时直接返回false（最小卡迈克尔数是561，且所有偶数都不可能是卡迈克尔数） - 分解质因数时没跳过重复因子，导致把
4或9当作合法因子参与(p−1)|(n−1)判断 - 用
int存n却在计算n-1后做模运算，遇到大数溢出——建议用long long，尤其当输入可能接近1e9
示例片段（核心逻辑）：
立即学习“C++免费学习笔记（深入）”；
bool isCarmichael(long long n) {
if (n < 561 || n % 2 == 0) return false;
vector<long long> factors;
long long t = n;
for (long long i = 2; i * i <= t; i++) {
if (t % i == 0) {
factors.push_back(i);
while (t % i == 0) t /= i; // 关键：去重并检测平方因子
if (n % (i * i) == 0) return false; // 有平方因子，出局
}
}
if (t > 1) factors.push_back(t);
if (factors.size() < 2) return false; // 至少两个不同素因子
long long n1 = n - 1;
for (long long p : factors) {
if (n1 % (p - 1) != 0) return false;
}
return true;
}
性能和边界要注意什么
对单个 n 判定，时间复杂度由质因数分解决定，最坏 O(√n)，对 n ≤ 1e12 可接受；但若需批量判定（比如筛出 1e6 范围内所有卡迈克尔数），硬套这个函数会超时。此时应预先筛出素数、再按 Korselt 构造候选数（例如枚举三素数乘积 pqr，检查是否满足 (p−1)|(pqr−1) 等）。另外，n=1 和 n=2 这类边界值必须显式排除，标准定义里卡迈克尔数从 561 开始，没有例外。
