0
我正在解決項目Euler question 58。這裏的正方形是從1開始,並以下面的方式盤旋逆時針(這裏是邊長等於7創建:我對歐拉#58項目的這個答案的錯誤在哪裏?
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
的問題是找出當我們不斷在廣場周圍盤旋,當比值對角線上的素數和對角線上的數字量小於0.10。
我確信我的解決方案使用下面的代碼(請參閱代碼註釋以獲得澄清),但該網站聲明答案錯誤時我正在輸入它
require 'prime'
# We use a mathematical derivation of the corner values, keep increasing the value till we find a ratio smaller
# than 0.10 and increase the grid_size and amount of numbers on diagonals each iteration
side_length = 3 # start with grid size of 3x3 so that we do not get into trouble with 1x1 grid
prime_count = 3 # 3, 5, 7 are prime and on a diagonal in a 3x3 grid
diagonal_size = 5
prime_ratio = 1 # dummy value bigger than 0.10 so we can start the loop
while prime_ratio >= 0.10
# Add one to prime count for each corner if it is prime
# Corners are given by n2 (top left), n2-n+1, n2-2n+2, and n2-3n+3
prime_count += 1 if (side_length**2).prime?
prime_count += 1 if (side_length**2-side_length+1).prime?
prime_count += 1 if (side_length**2-2*side_length+2).prime?
prime_count += 1 if (side_length**2-3*side_length+3).prime?
# Divide amount of primes counted by the diagonal length to get prime ratio
prime_ratio = prime_count/diagonal_size.to_f
# Increase the side length by two (full spiral) and diagonal size by four
side_length += 2 and diagonal_size += 4
end
puts side_length-2 #-2 to account for last addition in while-loop
# => 26612
這可能是錯誤的,網站是正確的。我現在陷入了這個問題很長一段時間。任何人都可以指出我的錯誤?
當然!!!在檢查變量時完全忽略了這一點。謝謝。 – 2014-08-30 16:47:01
另外,我認爲如果(side_length ** 2).prime?'可以刪除'prime_count + = 1,因爲一個正方形數字永遠不會成爲素數:} – ZomZom 2014-08-30 17:05:54
哇,以某種方式減少了50%以上的執行時間。 /編輯可能是因爲該值永遠不是素數,並且不是素數的數字需要更長時間才能檢查庫中的'prime?'函數。 – 2014-08-30 18:18:48