史密斯数必须是合数且各位数字和等于其所有质因数(含重复)的各位数字和;issmith()需先显式判断合数,排除质数(如13、97)和1,避免仅凭数字和相等误判。

不是所有数字和相等的合数都是史密斯数,但所有史密斯数必须同时满足:是合数、各位数字和等于所有质因数(含重复)的各位数字和。漏掉合数判断或质因数分解不彻底,就会把13、17这类质数误判为史密斯数。
isSmith() 必须显式排除质数,不能只靠数字和相等
常见错误是写成「只要 digit_sum(n) == sum_prime_digits(n) 就返回 true」。这会让 13、97 这类质数通过:它们的各位和等于自身(唯一质因数)的各位和,但史密斯数定义明确要求「合数」——即非质数且 > 1。
- 正确做法:开头先调用
is_composite(n)或内联判断,例如n > 1 && !is_prime(n) -
is_prime(n)要特判n == 1(既非质也非合)、n == 2(质数),然后试除到i * i - 别用
n != temp代替合数判断——比如n = 4分解后temp = 1,n != temp成立;但n = 9同样成立,而n = 25也成立,这个逻辑不等价于「是合数」
质因数分解时要边除边累加 digit_sum,不能只记因子种类
史密斯数要求质因数按重数展开,比如 8 = 2 × 2 × 2,就得算三次 digit_sum(2),而不是只加一次。如果只存因子集合或去重,8 就会错判。
- 循环从
i = 2开始,条件写成i * i ,避免浮点 <code>sqrt()精度问题 - 每遇到
temp % i == 0,就执行sum_prime_dig += digit_sum(i),再temp /= i,直到除尽 - 循环结束后若
temp > 1,说明剩下一个大于sqrt(原值)的质因数,必须再加一次digit_sum(temp) - 别用
std::vector存所有因子——单次判断没必要,还多一次遍历,直接累加更高效
digit_sum() 要稳,别用字符串或浮点函数
digit_sum(100) 必须返回 1,digit_sum(22) 返回 4。用字符串转换开销大、依赖 <string></string>;用 log10 有浮点误差风险;而取模法简洁可靠。
- 标准写法:
int digit_sum(int x) { int s = 0; while(x) { s += x % 10; x /= 10; } return s; } -
while(x)比while(x > 0)更通用(对正整数两者等价,且不引入额外比较) - 输入保证是正整数,所以不用处理负数;但若函数可能被复用,建议加
abs(x)防止-27 % 10在某些平台返回 -7 - 注意:
digit_sum(0)会返回0,但史密斯数定义域不含0,实际不会传入
i * i 可能溢出,大数要用 long long 或改判据
当 n 接近 INT_MAX(约 2.1e9)时,i 到 46340 左右,i * i 就会溢出成负数,导致循环条件恒真、死循环。
- 安全写法一:把循环变量声明为
long long i,并确保temp也升为long long(尤其当参数类型是long long时) - 安全写法二:改用
i 判据,整除无溢出,且语义等价 - 别信「我只测小数」——线上输入不可控,
i * i溢出是真实 crash 原因,不是理论风险 - 如果批量判断(如筛 1~10⁵ 内所有史密斯数),可预处理最小质因子(
spf数组),但单次判断完全没必要
真正容易被忽略的是「合数判定」和「残留大质因数」这两步——它们在样例 4、22、27 里不暴露问题,但在 58(=2×29)、121(=11×11)、97(质数)上立刻失效。写完务必拿这几个数手动过一遍逻辑。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











