史密斯数是合数且其各位数字之和等于所有质因数(含重复)的各位数字之和,如27(2+7=9,3×3×3→3+3+3=9);4也是史密斯数(4=2×2,4=2+2),而质数和1均不满足定义。

什么是史密斯数?先看判定逻辑
史密斯数不是质数,但它的各位数字之和等于其所有质因数(含重复)的各位数字之和。比如 27:
- 各位和是
2 + 7 = 9 - 质因数分解是
3 × 3 × 3,数字和是3 + 3 + 3 = 9
→ 所以 27 是史密斯数。
关键点:必须是合数(即非质数且 > 1),质数直接排除。
怎么写一个可靠的 isSmithNumber() 函数
核心分三步:判断是否为合数、算原数各位和、算质因数各位和。
容易错在质因数分解没处理重复因子,或忘了跳过质数:
- 用试除法分解时,每次找到因子后要持续除尽,比如
27遇到3后得除三次,不能只记一次3 -
sumOfDigits(n)要支持任意正整数,别硬写成三位数逻辑 - 特别注意
4:它是合数,质因数是2 × 2,各位和4 == 2+2→ 是史密斯数;而1不是合数,2是质数,都直接返回false
C++ 实现中几个易踩的坑
常见错误包括:isPrime() 把 1 判成质数、质因数循环漏掉最后剩下的大质数(如 97 在 97×2=194 中会被漏)、数字和函数对 0 处理不当(但输入是正整数,可不考虑)。示例片段:
int sumOfDigits(int n) {
int s = 0;
while (n) {
s += n % 10;
n /= 10;
}
return s;
}
<p>bool isSmithNumber(int n) {
if (n < 4) return false; // 最小史密斯数是 4
if (isPrime(n)) return false;</p><pre class='brush:php;toolbar:false;'>int originalSum = sumOfDigits(n);
int factorSum = 0;
int temp = n;
for (int i = 2; i * i <= temp; i++) {
while (temp % i == 0) {
factorSum += sumOfDigits(i);
temp /= i;
}
}
if (temp > 1) factorSum += sumOfDigits(temp); // 剩余大质数
return originalSum == factorSum;}
性能与边界要注意什么
对 n ≤ 10⁶,上面试除法够用;但若频繁调用,建议预筛质数表 + 分解优化。更隐蔽的问题是:史密斯数在稀疏分布中容易被误判——比如 22(2+2=4,质因数 2×11 → 2+1+1=4)是对的,但 30(3+0=3,质因数 2×3×5 → 2+3+5=10)就不是。别依赖“看起来像”来测试,务必走完整逻辑。
立即学习“C++免费学习笔记(深入)”;


















