C++如何判断一个长整数是否为史密斯数（Smith Number）-C++-PHP中文网

史密斯数是合数，且其各位数字之和等于所有质因数（含重复）的各位数字之和；需先判合数（如n1），再高效分解质因数并计算数字和。

c++如何判断一个长整数是否为史密斯数（smith number）

什么是史密斯数？先看判定逻辑

史密斯数是一个合数，且其各位数字之和等于它所有质因数（含重复）的各位数字之和。关键点有三个：必须是合数、不能是质数、数字和要严格相等。比如 27 是史密斯数：27 = 3 × 3 × 3，左边数字和是 2 + 7 = 9，右边是 3 + 3 + 3 = 9；而 13 不是，因为它是质数，直接排除。

如何高效分解长整数的质因数？

对 long long 范围内的数（如 10¹⁸），试除法必须优化——只试到 sqrt(n)，且优先处理小因子（2 和奇数）。别用筛法预处理，内存和时间都不现实；也别递归分解，栈容易溢出。

先特判 n == 1（不是合数）、n （最小合数是 4）
用 while (n % 2 == 0) 提取所有因子 2，每次累加 2 的各位数字（即 2）
然后从 3 开始，步长为 2，只试到 i * i ；每找到一个因子 <code>i，就不断除尽它，并累加 i 的各位数字
最后若 n > 1，说明剩下一个质因子（必大于 sqrt(原值)），把它各位数字加进去

数字和计算要注意什么？

digit_sum() 看似简单，但容易在负数、0 或大数取模时出错。C++ 中 % 对负数结果依赖实现，所以务必确保输入非负；另外，long long 的各位数字和最大不过 18×9 = 162，完全可用 int 存储，不必用大类型。

C++ Code Review Master

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

下载

写成循环 while (x) { sum += x % 10; x /= 10; } 即可，但必须保证 x > 0
对原始数调用前先检查是否为合数，否则跳过质因数分解
别把 1 当作质因数——它不是质数，也不参与分解

完整判断流程与边界坑点

最常踩的坑是漏判合数、误把质数当史密斯数，或质因数分解不彻底（比如剩个大质数没加进数字和）。下面这个骨架能跑通 long long 范围：

bool is_smith(long long n) {
    if (n // 处理因子 2
while (temp % 2 == 0) {
    sum_prime_dig += 2;
    temp /= 2;
    cnt_factor++;
}

// 处理奇因子
for (long long i = 3; i * i <= temp; i += 2) {
    while (temp % i == 0) {
        sum_prime_dig += digit_sum(i);
        temp /= i;
        cnt_factor++;
    }
}

if (temp > 1) {
    sum_prime_dig += digit_sum(temp);
    cnt_factor++;
}

// 必须是合数：至少有两个质因数（允许重复），即 cnt_factor > 1
return (cnt_factor > 1) && (sum_dig == sum_prime_dig);

}

注意 cnt_factor > 1 这个判断——它排除了质数（只被自己整除一次）和 1，但允许像 4（2×2）这样重复因子的情况。别用 is_prime() 单独判断，效率低且逻辑冗余。