史密斯数是合数n，其各位数字之和等于所有质因数（含重复）的各位数字之和；例如27=3×3×3，各位和9等于3+3+3=9，故为史密斯数。
什么是史密斯数？先看判定逻辑
史密斯数不是数学竞赛里那种靠查表或公式直接判断的数，它依赖两个实际计算步骤：分解质因数 + 比较各位数字之和。一个合数 n 是史密斯数，当且仅当：
-
n是合数（即不是质数，且 > 1） -
n的各位数字之和 == 它所有质因数（含重复）的各位数字之和
比如 27：
- 各位和 = 2 + 7 = 9
- 质因数分解是 3 × 3 × 3 → 所有质因子的各位和 = 3 + 3 + 3 = 9 → 是史密斯数
注意：质数永远不是史密斯数，1 也不是（既非质数也非合数）。
怎么写质因数分解函数？别用试除到 n
暴力试除到 n 太慢，尤其对接近 int 上限的数（如 2e9）。实际只需试除到 sqrt(n)，且每次除尽后立即累加该因子的各位和。
立即学习“C++免费学习笔记（深入）”；
- 如果循环结束后
n > 1，说明剩下一个大于sqrt(n)的质因子，要单独加进去 - 不需要存所有质因子，边分解边算各位和，省空间也省转换开销
int digitSum(int x) {
int s = 0;
while (x) { s += x % 10; x /= 10; }
return s;
}
<p>bool isSmith(int n) {
if (n < 4) return false; // 最小合数是 4，且 4=2×2 → 4 vs 2+2=4 → 是史密斯数
int sumN = digitSum(n);</p><pre class='brush:php;toolbar:false;'>int sumFactors = 0;
int temp = n;
for (int i = 2; i * i <= temp; ++i) {
while (temp % i == 0) {
sumFactors += digitSum(i);
temp /= i;
}
}
if (temp > 1) sumFactors += digitSum(temp); // 剩余大质因子
return sumN == sumFactors;}
为什么 4、22、27、58 是史密斯数，而 6、12 不是？看具体拆解
常见误判点在于忽略「合数前提」或漏掉重复因子：
-
6 = 2 × 3→ 各位和 6，因子数字和 2 + 3 = 5 → 不等 → 不是 -
12 = 2 × 2 × 3→ 各位和 1 + 2 = 3，因子数字和 2 + 2 + 3 = 7 → 不等 -
22 = 2 × 11→ 2 + 2 = 4，2 + 1 + 1 = 4 → 是 -
27 = 3 × 3 × 3→ 2 + 7 = 9，3 + 3 + 3 = 9 → 是
关键：质因数要按重数展开，27 的因子是三个 3，不是单个 3。
边界和性能要注意什么？
-
isPrime 不需要单独写——史密斯数定义排除质数，但你不能靠 !isPrime(n) 判合数，因为 1 也不是质数却不是合数。直接用 n > 1 && !isPrime(n) 不够严谨；更稳妥是：先排除 n < 4，再做分解，最后检查是否发生过分解（即是否至少有一个因子被除过，或 temp 被改过），否则就是质数
- 对于
n = 1e9 级别输入，i * i <= temp 可能溢出，建议用 i <= sqrt(temp) + 1 或把条件写成 i <= temp / i
- 输入为负数或 0？题目隐含正整数，但代码里最好加
if (n <= 0) return false; 防崩
isPrime 不需要单独写——史密斯数定义排除质数，但你不能靠 !isPrime(n) 判合数，因为 1 也不是质数却不是合数。直接用 n > 1 && !isPrime(n) 不够严谨；更稳妥是：先排除 n < 4，再做分解，最后检查是否发生过分解（即是否至少有一个因子被除过，或 temp 被改过），否则就是质数 n = 1e9 级别输入，i * i <= temp 可能溢出，建议用 i <= sqrt(temp) + 1 或把条件写成 i <= temp / i if (n <= 0) return false; 防崩 真正容易卡住的地方，不是算法逻辑，而是忘记 27 这种全同质因子的情况要反复加同一数字，以及漏掉最后那个大质因子。
