史密斯数是合数且其各位数字之和等于所有质因数(含重复)的各位数字之和;例如4=2×2,数字和4=2+2,故为史密斯数;质数和1均不符合定义。

什么是史密斯数,以及为什么不能只看数字和
史密斯数不是各位数字之和等于某值的数——它要求:合数、各位数字之和 == 其所有质因数(含重复)的各位数字之和。比如 27 是合数,数字和是 2 + 7 = 9;质因数分解为 3 × 3 × 3,质因数数字和是 3 + 3 + 3 = 9,所以它是史密斯数。质数自动排除,1 也不是(既非质数也非合数),4 是最小的史密斯数(4 = 2×2,数字和 4 == 2+2)。
如何正确分解质因数并累加各位数字
暴力试除即可,但要注意两点:一是循环到 sqrt(n) 就够了,二是最后若 n > 1,说明剩余的 n 本身是质因数(且只出现一次)。每次得到一个质因数 p,就调用辅助函数算它的各位数字和,并累加。
示例片段(核心逻辑):
int digitSum(int x) {
int s = 0;
while (x) { s += x % 10; x /= 10; }
return s;
}
<p>bool isSmith(int n) {
if (n 1) sumPrimeDigits += digitSum(temp); // 剩余大质因数
return sumDigits == sumPrimeDigits;
}</p>
容易漏掉的关键判断点
常见错误是忽略「必须是合数」这一前提,直接对所有 ≥ 4 的数判断。这会导致质数被误判——比如 11 数字和是 2,质因数只有它自己,数字和也是 2,但它不是合数,不能算史密斯数。
- 先用简单试除或
is_prime判断是否为质数,若是,直接返回false - 注意
4、6、8、9这些小合数要能过,尤其是9 = 3×3,数字和9 == 3+3✔️ -
digitSum(10)是1,但10 = 2×5,质因数数字和是2+5 = 7,不等 → 正确排除
C++ 实现时的边界与性能提醒
对单个整数判断,O(√n) 完全够用;但如果批量判断(比如 1~10000),可以预处理最小质因数(spf 数组)加速分解,不过日常使用没必要。真正要注意的是:
-
int范围内(如2e9以内)没问题,但sqrt(n)计算别用sqrt(n)函数(浮点误差),写成i * i - 不要在循环里反复调用
digitSum对同一个质因数(比如2出现 10 次),应每分解出一个因子就立即加一次 -
digitSum(0)会返回 0,但输入不会是 0;digitSum对负数未定义,确保输入为正整数
史密斯数稀疏且无显式公式,判断逻辑本身不复杂,但「合数」和「质因数数字和」这两步缺一不可,漏掉任一,结果就不可靠。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











