卡迈克尔数是满足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
示例片段（核心逻辑）：
n
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
