查找数字总和为素数的数字

Question

我试图在SPOJ上解决这个问题,我必须找到一个数字总和为素数的范围内有多少个数字.该范围可以非常大,(给出10 ^ 8的上限).天真的解决方案超时,我只是在整个范围内循环并检查所需的条件.我似乎也找不到模式或公式.有人可以指示继续吗？

提前致谢...

Answer 1

以下是一些提示:

尝试编写一个函数,查找给定范围内有多少数字具有给定的数字总和.实现这一点的最简单方法是编写一个函数,该函数返回给定数字总和的数字数量,直到给定值a(调用此f(sum,a)),然后在a到a的范围内返回这些数字的数量b将是f(sum,b) - f(sum,a - 1)
注意数字本身的总和不会太高 - 高达8*9 <100因此要检查的素数总和很小

希望这可以帮助.

最简单的方法是进一步分解问题 - 找到具有给定位数d的数字x的数量,并且这些数字的总和等于总和.对于每个这样的问题,我建议使用dp方法,其中dp是二维的 - 一个维度用于总和左边,第二个维度用于剩余的数字.所以现在你必须计算g(d,sum,a).我可以提供解决问题的代码,但SPOJ中的想法是让用户自己提出解决方案. (2认同)