发现号的数字之和为一个素数 [英] Finding numbers whose digits sum to a prime

问题描述

我试图解决这个问题的SPOJ，在此我必须找到多少个号码里有一系列的数字总结为一个素数。这个范围是非常大的，（上限为10 ^ 8给出）。天真的解决方案超时，我只是环绕在整个范围内，并检查所需要的条件。我似乎无法找到一个模式或公式了。可能有人请给一个方向着手??

I was trying to solve this problem on SPOJ, in which I have to find how many numbers are there in a range whose digits sum up to a prime. This range can be very big, (upper bound of 10^8 is given). The naive solution timed out, I just looped over the entire range and checked the required condition. I cant seem find a pattern or a formula too. Could someone please give a direction to proceed in??

在此先感谢...

推荐答案

下面是一些提示：

• 尝试写一个函数，找到多少个号码给定范围内拥有的数字给定的总和。最容易实现这种方式写出一个函数，返回号码的数目与位的给定总和达到一个给定的值（称之为F（总和，a））和然后这些数字的范围内的数B将被F（总和，B） - F（总而言之， - 1）
• 注意的的数字之和本身不会太高 - 高达8 * 9＆LT; 100，所以黄金的款项，检查的数量是非常小的

希望这有助于。

这篇关于发现号的数字之和为一个素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！