卡迈克尔数是满足费马小定理伪素数行为的无平方因子合数：n>2且为合数，对每个素因子p均有(p−1)∣(n−1)，且n无平方因子。判定必须通过素因子分解并逐项验证三条件。
什么是卡迈克尔数？先看判别条件
卡迈克尔数不是素数，但满足费马小定理的“伪素数”行为：对所有与它互质的整数 a，都有 a^n ≡ a (mod n)。等价地，n 是合数，且对每个它的素因子 p，都有 (p−1) | (n−1)，同时 n 无平方因子（即每个素因子只出现一次）。
所以判断一个整数 n 是否为卡迈克尔数，必须同时满足：
-
n > 2且为合数（不能是素数，也不能是 1 或 2） -
n是无平方因子的（即分解后所有指数均为 1） - 对
n的每个素因子p，(n−1) % (p−1) == 0
如何高效分解 n 并检查无平方因子
暴力试除到 sqrt(n) 是可行起点，尤其对 n ≤ 10^9 的常见测试范围足够快。关键是边分解边验证：
- 遇到某个素因子
p能整除n多次（即n % (p*p) == 0），立刻返回false（含平方因子） - 每个新素因子
p记录下来，用于后续模条件检查 - 最后若剩余部分
r > 1，它本身也是素因子（且只出现一次）
示例片段逻辑：
vector<int> factors; int temp = n; for (int i = 2; i * i 1) factors.push_back(temp); // 剩余大素因子</int>
为什么不能跳过素性检验直接用费马测试
有人想用多次 pow(a, n, n) == a % n 来“验证”，这是危险的：
- 卡迈克尔数定义要求对所有与
n互质的a成立，你不可能穷举 - 即使随机选 10 个
a都通过，也不能证明是卡迈克尔数（可能是普通伪素数） - 更糟的是：某些合数对部分
a满足同余，但不满足全部素因子条件，会被误判
真正可靠的判别只有一条路：素因子分解 + 三条件逐项校验。
边界和易错点提醒
-
n = 561 是最小卡迈克尔数，务必用它测通：因子为 [3,11,17]，560 % 2 == 0、560 % 10 == 0、560 % 16 == 0 ✔️
-
n 必须是奇数（偶数合数必含因子 2，而 2−1=1 虽整除任何 n−1，但其他因子如 4 出现时会违反无平方因子；实际已知所有卡迈克尔数都是奇数且 ≥ 3 个素因子）
- 不要漏掉“
n 是合数”这一前提：若 is_prime(n) 返回 true，直接 false
-
int 范围内（≤ 2³¹−1）最大的卡迈克尔数是 1020971904，分解时注意 i*i 可能溢出，建议用 i 或 <code>i
n = 561 是最小卡迈克尔数，务必用它测通：因子为 [3,11,17]，560 % 2 == 0、560 % 10 == 0、560 % 16 == 0 ✔️n 必须是奇数（偶数合数必含因子 2，而 2−1=1 虽整除任何 n−1，但其他因子如 4 出现时会违反无平方因子；实际已知所有卡迈克尔数都是奇数且 ≥ 3 个素因子）n 是合数”这一前提：若 is_prime(n) 返回 true，直接 false
int 范围内（≤ 2³¹−1）最大的卡迈克尔数是 1020971904，分解时注意 i*i 可能溢出，建议用 i 或 <code>i
真正卡迈克尔判定的难点不在算法结构，而在分解过程里对平方因子的即时拦截、以及对每个因子做 (n−1) % (p−1) 时的整除逻辑是否写反——这里最容易把条件写成 (p−1) % (n−1)。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
