Project Euler Problem 27

問題

Euler published the remarkable quadratic formula:

n^2 + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to
39. However, when n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41,
and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n^2 − 79n + 1601 was discovered,
which produces 80 primes for the consecutive values n = 0 to 79. The product of the
coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

    n^2 + an + b, where |a| < 1000 and |b| < 1000

    where |n| is the modulus/absolute value of n
    e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that
produces the maximum number of primes for consecutive values of n, starting with n = 0.

ソース

max = 100000
@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

def count_prime(a, b)
	n = 0
	while true
		x = n * n + a * n + b
		break if x < 0 || @prime[n * n + a * n + b].zero?
		n += 1
	end
	n
end

ans = 0
max = 0
-999.upto(999) do |a|
	-999.upto(999) do |b|
		n = count_prime(a, b)
		ans, max = a * b, n if max < n
	end
end
puts ans

解答

-59231

感想

んま全探索で終わったので良かった。。
こういう問題の場合、素数をどこまで用意するかが不明なんよな（汗