K-Smith numbers
Smith number 是自身数字和等于其所有素因子（包含重复）的数字和的合数。比如：666=2*3*3*37
666的数字和为：6+6+6=18；而666的所有素因子（包含重复）的数字和为：2+3+3+3+7=18，于是，666是一个Smith number。
更奇特的，三个相邻合数73615 ，73616，73617都是Smith number（73615=5*14723 ，73616=(2^4)*43*107，73617=3*53*463）。我们把K个相邻合数都是Smith number的数称为K-Smith numbers ，为了方便，就以第1个合数来表示这K个数。比如，73615 ，73616，73617，表示为3-Smith numbers : 73615。
问题：
1）：请求出10^12内的所有3-Smith numbers。
2）：对1<=i<=10中的每个i，请求出i-Smith numbers各一个
[ 本帖最后由 medie2005 于 2008-11-21 16:30 编辑 ] Smith number，这个我到是见过，我是在一个业余数学天地的网站上看到的。 medie找到什么好的想法了吗？
通常同进制相关的东西很难有特别有效的方法，感觉$10^19$的范围也太大了一些 是，大了很多，Smith number太多了。:L 我的想法是穷举，但没想出什么好的剪枝算法。
算法思路：
1. 采用筛法，批量分解质因数。应该比逐个分解质因数快不少。需要用到链表（可用内存池优化性能），也需要不少的内存。
2. .对于每个合数，计算其各位数字之和，和各个素因数各个数字之和。
复杂是O(n)的算法，不知大家有没有想到更好的算法。
对了，当n<10^19,谁能给出每个数的素因素的个数的平均值 $logn$吧 平均值应该不是这么简单吧。不过每个数的素因子个数的上限是$log_2{n}$, 因为因子越小，因子个数越多，对于形如2^k的数，如1048576，他的每个因子都达到最小值，因此因子个数达到最大值$log_2{n}$ 我有个想法，也许可以将总搜索过程降低将近一个数量级。
对于每个整数a,记N(a)为a的所有数字之和，P(a)为a的所有素因子的数字之和。那么我们就是要找N(a)-P(a)=0的所有的数。
我们知道如果N(ab)=P(ab)=P(a)+P(b),两边同时对9取余数，我们得到$N(a)xxN(b)-=P(a)+P(b)(mod 9)$
如果我们对一个比较小的范围内所有的都事先计算好N(a),P(a),然后将它们的值模9分类，共可以分成81类。然后它们之间两两组合平均应该只有1/9满足上面同余式，这样我们应该可以消去一些工作量 不是$log_2 n$是$ln n$
回复 9# 无心人 的帖子
这两个数只差了一个很小的因子。另外，我估计平均因子个数应该小于$log(n)$