求下个史密斯数 算法史密斯数是指每位数字之和,与所有质因数的每位数字之和相等的数,比如:4937775 = 3 × 5
![](images/u2507.png)
求下个史密斯数 算法
史密斯数是指每位数字之和,与所有质因数的每位数字之和相等的数,比如:
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)
这个算法算出来的是对的,但是当数字变大时就变得很慢,甚至会发生算不出来的现象,应该怎么改进啊?
史密斯数是指每位数字之和,与所有质因数的每位数字之和相等的数,比如:
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)
这个算法算出来的是对的,但是当数字变大时就变得很慢,甚至会发生算不出来的现象,应该怎么改进啊?
已提交,审核后显示!提交回复
共1条回复
david6 共回答了18个问题
|采纳率83.3%- 提前算好需要范围内的史密斯数,列一张表.
然后在运行时只进行简单的查找就可以了.
似乎没有复杂度很低的验证算法.因为分解质因数这个事本身就很难. - 1年前
相关推荐
大家在问
- 1x-12分之5=8分之3 4分之3+x-4=2分之1
- 2I answered his telephone call.then I wrote him a letter (aft
- 3汉语拼音里的韵目有哪些
- 4(2008•广州)某岛上生存着桦尺蠖的两个变种,该地区原为森林,后建设为工业区.下表为该地区不同时期变种桦尺蠖的数量比,
- 5英语翻译就像一个忠诚的仆人,永远等待着你的召唤
- 6一个环形,内圆周长9.42,环宽2厘米可以求得内圆半径是( )厘米,外圆半径是()厘米
- 7无数的“数”是3声,还是4声?
- 8用英语翻译“ 问题是我们的钱已经用完了 ”这句话
- 91又15分之1等于几时
- 10计算下面各题,能简便的要简算.1 4 5 ×37.5%- 3 8 ×0.8-0.375 3 11 ÷7+ 6 7 × 3
- 11马说 以呜呼的感叹收束全文表达了作者怎样的感情
- 12在一张长方形纸上剪下两个相同的小圆,剩下的部分正好可剪出一个正方形,如右图,求所剪正方形的周长和面积.
- 13下列说法错误的是( )A.近似数0.8与0.80表示的意义不同B.近似数0.2000有四个有效数字C.3.450×10
- 14形容人小巧的成语,要褒义词
- 15妈妈对我说:''你好好养病吧,我已经向你的老师请假了.''(改为第三人称转述句)