Project Euler Problem 50

Ruby

問題

The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains
21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

ソース

max = 1000000
prime = Array.new(max, 1)
prime[0..1] = [0, 0]
i = 2
while i < Math.sqrt(max).to_i + 1 do
	(i + i).step(max, i){|x| prime[x] = 0}
	i += prime[(i + 1)..max].index(1) + 1
end

len = 0
ans = 0
array = prime.each_index{|i|
	prime[i] = i unless prime[i].zero?
}.select{|x| !x.zero? }
array.each_index{|i|
	count = 0
	array[i...array.size].inject(0) {|s, x|
		s += x
		break if s >= max
		count += 1
		ans, len = s, [len, count].max if !prime[s].zero? && len < count
		s
	}
}
puts ans

解答

997651

感想

O(N^2)となるので、かなり時間のかかりそうな計算に思えたが、以外に数秒で終わった。