幸運數字或不

可能重複：
Algorithm to find Lucky Numbers 幸運數字或不

我碰到這個question.A號來到被稱爲幸運的，如果它的數字的總和，還有的總和其數字的平方是一個素數。 A和B之間有多少數字是幸運的？ 1 < = A < = B < = 10^18。

我試過這個，首先我生成了1和可以通過求和的平方數（81 * 18 = 1458）得到的數字之間的所有可能的素數[注意：我使用了Atkin方法生成素數的篩選] 。
然後驗證每個數字的數字總和和數字平方和是否在素數列表中，如果是的話否則不幸運。但是這非常慢。有沒有更好的解決方法？

2012-02-12 siva

你可以請你縮進你的代碼嗎？會讓它更容易閱讀。 – 2012-02-12 14:35:28

Java庫在C中不能正常工作..... – 2012-02-12 14:36:33

'h'和'q'被聲明但沒有被使用。 – DNA 2012-02-12 14:42:02

看看我很好解釋這裏的解決方案：Algorithm to find Lucky Numbers（請注意 - 你的問題是這樣的一個的副本）。

2012-02-12 15:08:14 OleGG

只需聲明一個大小爲1458的位數組，然後將該位設置爲true，如果該位是質數，則返回true，否則設置爲false。然後確定一個給定的數字是否爲素數只是查找數組的相應元素。

素數計算有很多解釋，即Eratosthenes篩，Atkin篩等。使用其中之一來初始化陣列。

2012-02-12 14:43:27

這是正確的，但我的主要問題是我的輸入。我必須檢查每一個數字（如果它被給予10^18。我必須檢查從1到10^18需要更多的時間），所以它花了很多我們如何減少 – siva 2012-02-12 14:49:13

質數查詢以外，您正在做的其他事情是I/O，求和和相乘整數以及數組查找。爲了加速這些事情，您基本上需要更改語言或硬件，但我認爲這超出瞭解決方案的範圍。 – 2012-02-12 14:51:16

我的問題不是關於生成素數，而是關於檢查一個數字是否幸運 – siva 2012-02-12 14:52:03

回答