Project Euler Problem 46

問題

It was proposed by Christian Goldbach that every odd composite number can be
written as the sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and
twice a square?

ソース

require 'mathn'

max = 10000
$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

prime_array = $prime.each_index{|i|
  $prime[i] = i unless $prime[i].zero?
}.select{|x| !x.zero?}

class Integer
  def composite?
    pd = self.prime_division
    return false unless pd.inject(0){|s, x| s + x[1]} >= 2
      pd.all?{|x|
      !$prime[x[0]].zero?
    }
  end
end

3.step(prime_array.last, 2){|i|
  next if !i.composite?
  if prime_array.select{|x| x <= i}.find{|x| (i - x) / 2 == Math.sqrt((i - x) / 2).floor ** 2}.nil?
    puts i
    break
  end
}

解答

5777

感想

PCが無い時代だったら5777まで現れなかったら、このような予想が出てくるのも無理がない！
これも、問題通り実装するだけで解けるかな！