查找其數字總和爲素數的數字

我試圖解決SPOJ上的這個問題，在這個問題中我必須找到在其數字總和爲素數的範圍內有多少數字。這個範圍可以很大，（給出10^8的上限）。天真的解決方案超時，我只是在整個範圍內循環，並檢查所需的條件。我似乎無法找到一種模式或公式。有人可以給一個方向繼續前進？查找其數字總和爲素數的數字

在此先感謝...

2012-03-27 frodo

使用埃拉托色尼的篩子到最大總和（9 + 9 ......）生成素數。把它們放在哈希表中。然後你可能很快通過10^8的數字循環並加起來。可能有更有效的方法，但這應該足夠快。

2012-03-27 12:47:16

我懷疑它會有很大的影響，因爲所需素數的範圍是'[1,72]' – amit 2012-03-27 12:49:15

@amit 10^7花了17秒，所以我猜10^8會花費10倍。這顯然不是最好的方式。但是，如果要求不低於1分鐘，那麼代碼很少，而且易於理解。 – 2012-03-27 13:02:28

我已經跑了10^8，花了3:11。 – 2012-03-27 13:07:55

這裏有一些提示：

嘗試編寫發現多少個號碼在特定範圍內具有的數字給定和的功能。實現這一點最簡單的方法是編寫一個函數，該函數返回給定數值總和達到給定值a（稱爲f（sum，a））的數字數量，然後返回範圍a到b將是f（sum，b） - f（sum，a - 1）
請注意，數字本身的總和不會太高 - 最多爲8 * 9 < 100因此，檢查是真的很小

希望這會有所幫助。

2012-03-27 12:50:02

範圍是[[1,72]'[99999999]]。除此之外 - 非常好的解決方案。 +1 – amit 2012-03-27 12:51:29

@amit上限是10^8，所以實際上，範圍是[1,72]，正如我在回答中所述。我只是指出，這是不到100的，所以沒有問題來遍歷該範圍內的所有素數。 – 2012-03-27 12:54:14

我指的是你的回答的前一個版本，其中指出'18 * 9 <200'數字，並希望給予更嚴格的界限。 – amit 2012-03-27 12:55:19

我（嚴重）懷疑這個「相反」的做法是否會比任何@ izomorphius的建議更快，但它可能會促使有關提高程序性能的一些想法：

1）獲取素數的列表範圍2..71（因爲它們都不是素數，所以可以忽略1和72）。

2）枚舉列表中每個素數的整數分區。這裏有一些Python code。你需要修改這個以免生成無效的分區，例如那些包含大於9的數字。

3）對於每個分區，用0填充一組8位數字，然後枚舉填充集合的所有排列。

現在你有你需要的數字列表。

2012-03-27 13:40:05

回答