求下个史密斯数算法史密斯数是指每位数字之和,与所有质因数的每位数字之和相等的数,比如：4937775=3×5×5×65837,4+9+3+7+7+7+5=3+5+5+6+5+8+3+7=42现在如果给定任意一个

Question

求下个史密斯数 算法
史密斯数是指每位数字之和,与所有质因数的每位数字之和相等的数,比如：
4937775 = 3 × 5 × 5 × 65837,4 + 9 + 3 + 7 + 7 + 7 + 5 = 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42
现在如果给定任意一个数字,返回离它最近的史密斯数（0和质数排除在外）
由于是用Haskell写的,所以无法用到C或者Java里的array,我的算法是：
先检测一个数n是否为质数,如果是,则试n+1
然后检测n+1的各位数和 与 n+1的质因数和 是否相等,若相等,返回n+1
否则再测试n+1
检测是否为质数的算法是：
若为2则为质数
若为1或为偶数则返回False
然后从3开始,一个奇数一个奇数试,一直试到这个数的平方根为止
将各位数字相加的算法是：
如果小于10则返回这个数
否则除以10的余数 + sumDigit (n `div` 10)
这个算法算出来的是对的,但是当数字变大时就变得很慢,甚至会发生算不出来的现象,应该怎么改进啊?

Answer 1

提前算好需要范围内的史密斯数,列一张表.
然后在运行时只进行简单的查找就可以了.
似乎没有复杂度很低的验证算法.因为分解质因数这个事本身就很难.