爲什麼我的代碼不會運行？

我正在努力解決Project Euler中的Problem #5。代碼適用於這個例子，當我檢查從1到10的數字時，我得到了2520，這是正確的。但是當我檢查從1到20的數字時，代碼不會停止運行。爲什麼我的代碼不會運行？

這就是：

num = 0 

while true 

    num += 1 
    check = true 

    for i in 1..20 

     break unless check 

     check = num%i==0 

    end 

    break if check 

end 

File.open("__RESULT__.txt", "w+").write num

來源

2010-06-04 Vincent

Marc已經給出了完美的答案。或者：因爲每個數字必須被20整除，'num + = 20'會給你20倍的加速。另外，使用'for i in 2..20'，因爲每個數字都可以被1整除 – schnaader 2010-06-04 12:40:41

作爲樣式註釋：您的代碼可能更習慣性地寫爲'inf = 1.0/0.0; num =（1..inf）.find {| n | （1.20）。所有？ {|我| x％i == 0}}' - 但這不會改變計算時間太長的事實。 – sepp2k 2010-06-04 12:41:40

剛剛檢查了我在Ruby中提出的稍微優化的版本。這需要大約1分鐘，這對於歐拉項目來說很難，並且比我的C++版本慢2秒鐘。 – schnaader 2010-06-04 12:48:11

該問題的解決方案不能僅僅計算每一個可能的解決方案中找到。解決方案如此之大，以至於需要數天（甚至數年）才能計算出來。

有一個聰明的解決方案，使用素數來記錄數字。

所給出的例子（2520是是divisable由數字1到10的最小數目）可以寫成下這樣：

1 = 1 (can be skipped) = 2^0 * 3^0 * 5^0 * 7^0 
2 = 2 (prime)   = 2^1 * 3^0 * 5^0 * 7^0 
3 = 3 (prime)   = 2^0 * 3^1 * 5^0 * 7^0 
4 = 2^2     = 2^2 * 3^0 * 5^0 * 7^0 
5 = 5 (prime)   = 2^0 * 3^0 * 5^1 * 7^0 
6 = 2 * 3    = 2^1 * 3^1 * 5^0 * 7^0 
7 = 7 (prime)   = 2^0 * 3^0 * 5^0 * 7^1 
8 = 2^3     = 2^3 * 3^0 * 5^0 * 7^0 
9 = 3^2     = 2^0 * 3^2 * 5^0 * 7^0 
10= 2 * 5    = 2^1 * 3^0 * 5^1 * 7^0

現在可以通過這些被劃分的最小數目，

2^3 * 3^2 * 5^1 * 7^1 = 2520

同樣可以（甚至用手）上的數字來執行1至20

：可以通過使用在每個原使用的最大功率來計算最後提示：答案是比100.000.000一個十億較大，但更小，所以它可以被在幾分鐘內，如果有效地完成計算

來源

2010-06-04 12:36:32 Marc

謝謝！我首先手工完成（在閱讀我們的答案之後），然後優化我的代碼，現在兩種方法都可以工作！ – Vincent 2010-06-04 13:30:19

問題本質要求你找到的第20號的LCM。 ..

lcm = 1 
for i = 2 to 20 
    lcm = (i * lcm)/gcd(lcm,i)

來源

2010-06-09 09:22:36 st0le

一個更簡單的解決方案是使用你的算法，但增加2520而不是1，這裏是我的C++解決方案。

#include <iostream> 
using namespace std; 

int main() 
{ 
    int check = 2520; 
    int i = 11; 
    while (i != 20) 
    { 
     i ++; 
     if (check % i != 0) 
     { 
      check +=2520; 
      i = 1; 
     } 
    } 
    cout << check << endl; 
    return 0; 
}

正如你可以在上面看到，我也開始在號碼2520，令i等於11，我們可以讓這些優化操作，因爲我們已在該問題的必要信息。

來源

2010-09-29 12:42:40 ajnatural

爲什麼我的代碼不會運行？

回答

相關問題