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

卡迈克尔数是满足korselt准则的合数：非素数、无平方因子、且对每个质因数p都有(p−1)∣(n−1)；三者缺一不可，否则会误判素数或含平方因子的数。

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

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

卡迈克尔数不是素数，但满足费马小定理的“伪素性”：对所有与它互质的整数 a，都有 a^n ≡ a (mod n)。等价判定条件（Korselt准则）更实用：

n 是合数（即非素数且 > 1）
n 无平方因子（即每个质因数只出现一次）
对 n 的每个质因数 p，都有 (p − 1) | (n − 1)

这三条必须同时成立，缺一不可。很多人只检查最后一条，漏掉前两条，导致把素数或含平方因子的数误判为卡迈克尔数。

如何高效分解质因数并验证无平方因子

暴力试除到 sqrt(n) 是最稳妥的做法，尤其对 n ≤ 10^6 完全够用。注意两点：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

边分解边检查重复因子：若某质因数 p 能整除 n 两次（即 n % (p * p) == 0），直接返回 false
最后剩余的 n > 1 是一个大质因数，也要纳入检查列表
不要用筛法预处理——单次判断没必要，且内存和初始化开销反而高

vector<int> factors;
int temp = n;
for (int i = 2; i * i  1) factors.push_back(temp);
</int>

验证 (p−1) 整除 (n−1) 时的常见错误

最容易出错的是整数溢出和边界情况：

n 为 2 或 3 时，直接是素数，应提前 return false
计算 (n - 1) % (p - 1) 前，确保 p > 1（总是成立），但要注意 p == 2 时 p - 1 == 1，模 1 恒为 0，没问题
若用 long long 存 n，别忘了 p 和 n-1 都在 int 范围内，但模运算本身不溢出；真正风险在 i * i 中的乘法——用 <code>i 更安全

完整逻辑顺序不能乱：先判合数（即不是素数且 > 1），再分解，再验无平方，最后验整除性。跳过合数检查，561 过得去，但 7 也会被误判。

实际可用的 C++ 函数骨架

bool isCarmichael(int n) {
    if (n  factors;
    int temp = n;
    for (int i = 2; i  1) factors.push_back(temp);
    int n_minus_1 = n - 1;
    for (int p : factors) {
        if (n_minus_1 % (p - 1) != 0) return false;
    }
    return true;
}

其中 isPrime 只需朴素实现（试除到 sqrt(n)）。卡迈克尔数极稀疏（比如 10⁶ 内只有 4 个），所以不用过度优化。真正要盯住的是：合数判断、平方因子检测、整除验证三者缺一不可——少一个，561 可能过，但 1105 或 1729 就会翻车。