2014-08-30 52 views
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 

这可能是错误的,网站是正确的。我现在陷入了这个问题很长一段时间。任何人都可以指出我的错误?

回答

3

side_length += 2 and diagonal_size += 4应该在循环的开始处。

无法检查,我没有安装ruby,但我可以在我的python解决方案上重现相同的问题。

+0

当然!!!在检查变量时完全忽略了这一点。谢谢。 – 2014-08-30 16:47:01

+2

另外,我认为如果(side_length ** 2).prime?'可以删除'prime_count + = 1,因为一个正方形数字永远不会成为素数:} – ZomZom 2014-08-30 17:05:54

+0

哇,以某种方式减少了50%以上的执行时间。 /编辑可能是因为该值永远不是素数,并且不是素数的数字需要更长时间才能检查库中的'prime?'函数。 – 2014-08-30 18:18:48