C++如何判断一个整数是否为卡迈克尔数(Carmichael Number 判别)-C++-PHP中文网

卡迈克尔数是满足korselt准则的合数：无平方因子，且对每个素因子p都有(p−1)∣(n−1)；需先排除素数、偶数及n

c++如何判断一个整数是否为卡迈克尔数(carmichael number 判别)

什么是卡迈克尔数？先看判别条件

卡迈克尔数是合数 n，且对所有与 n 互质的整数 a，都满足 a^(n−1) ≡ 1 (mod n)。但直接枚举所有 a 显然不可行。实际判别用的是等价的**Korselt 准则**：
一个合数 n 是卡迈克尔数 ⇔ 对 n 的每个素因子 p，都有 (p − 1) | (n − 1)，且 n 是无平方因子的（即每个素因子只出现一次）。

如何分解质因数并验证 Korselt 条件

核心步骤是：先试除得到所有不同质因子，同时检查是否含平方因子；再对每个质因子 p 检查 (n − 1) % (p − 1) == 0。注意：
- n 必须是合数（不能是质数，也不能是 1）
- 质因数分解只需到 sqrt(n) 即可
- 若最后剩余的 n > 1，它本身是一个质因子（且指数为 1，否则已含平方因子）

常见错误现象：
- 忘记检查 n 是否为合数，导致质数被误判（如 7 满足 Korselt 但不是卡迈克尔数）
- 未验证无平方性，把 12 = 2²×3 当作候选（其实 2² 已违反条件）
- 对大数（如 n > 1e9）暴力试除太慢，但卡迈克尔数本身稀疏，实际测试中 n 就够覆盖前几十个

示例逻辑片段：

bool isCarmichael(int n) {
    if (n  1) return false; // 含平方因子
            if ((n - 1) % (p - 1) != 0) return false;
        }
    }
    if (temp > 1) { // 剩余大质因子
        if ((n - 1) % (temp - 1) != 0) return false;
    }
    return true;
}

`isPrime` 怎么写才不拖慢整体判断

卡迈克尔数最小是 561，所以 n 通常不小，但 isPrime 只需用于初步过滤——若 n 是质数，直接返回 false。这里不需要 Miller-Rabin，普通试除即可，但要注意优化：
- 只需检查到 sqrt(n)
- 先特判 2，再只试奇数
- 对小 n（如 ）可直接查表或硬编码

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

容易踩的坑：
- 把 sqrt(n) 写成 sqrt(n)+1 导致浮点误差（建议用 i * i ）<br>- 忘记 <code>n == 2 时返回 true，结果 2 被误判为合数，进而影响后续逻辑
- 在 isCarmichael 中重复调用 isPrime 和质因数分解，其实两者可合并：分解过程中若发现只有一个因子且等于 n，说明 n 是质数

几个典型测试用例与边界行为

验证实现是否靠谱，得盯住这几个关键值：
- 561：最小卡迈克尔数（3×11×17），必须返回 true
- 4：合数但含平方因子（2²），应返回 false
- 17：质数，应返回 false
- 1 或 0：非正整数，按定义不属于卡迈克尔数，返回 false
- 1105：第二个卡迈克尔数（5×13×17），(1105−1)=1104 能被 4、12、16 整除，应返回 true