计算幸运数 算法问题

LucEsape 发布于 2014/01/24 08:47
阅读 443
收藏 1

如果一个数各个数位上的数字之和是质数,并且各个数位上的数字的平方和也是质数,则称它为幸运数。给定x,y,求x,y之间( 包含x,y,即闭区间[x,y])有多少个幸运数,限时3秒

例如1到20之间有4个幸运数,它们是11,12,14,16,像因为1+1 = 2是质数,1^2 + 1^2 = 2也是质数等等。给定函数原型,其中1<=x<=y<=1000000000。

说明是讨论算法,并非是求解,吐槽请绕道。

特别邀请 @中山野鬼 前来指点迷津

加载中
0
Zoker
Zoker
这种题目Google 有好多,下载一个好好研究下
0
中山野鬼
中山野鬼

哈,排除法是最基本的。我的理解是单次扫描。多项排除。

这里有个问题是排除的判断,需要一个素数表,做比较。如果素数表不存在,则上述排除法中需要包含一些素数构造的条件。例如 , abc 三位数, a+b+c 并不等于素数。而我们知道,非素数 + 6 肯定也不是素数,那么 ab(c+6)自然可以直接排除掉。例如 ,103 对应的 ,109 ; 441 对应的 447  

LucEsape
LucEsape
谢谢老鬼的解析
0
hecaptain
hecaptain

质数的个数不多,何不反过来思考呢

首先知道了x,y,那么就知道了各个数位上的数字之和的最大值

如[1,20]最大就是10,如[100,999]最大就是27

然后通过最大值里面的质数反推就好了

比如最大为10,那么可能的质数就是2,3,5,7,再分析各个质数的组合

通过x和y的大小来排除大多可能,1位数肯定是不行的,因为他的平方肯定不是质数

那么2,3,5,7 剩余的可能只有11,12,14,16(想21之类由y值剔除了)

然后再判断11,12,14,16的各位平方和就好


就算20位数最大也就180,里面的质数也才几十个,各种组合不多,复杂度很低

LucEsape
LucEsape
结合老鬼的 就完美了。
0
应建伟1986

http://www.xuebuyuan.com/527810.html

最佳解答。楼上的思路不错,实现有点困难。


返回顶部
顶部