読者です 読者をやめる 読者になる 読者になる

mu chance or much chance ?

日々の戯れ言

Project Euler 46

Project Euler

Problem46を解きました.

  • Goldbach's other conjecture

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×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

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?

https://projecteuler.net/problem=46

問題は「平方数の2倍と素数の和で表せない最小の合成奇数はいくつか求めよ.」.

require 'prime'

i = 3
loop do
  if Prime.prime?(i)
    i += 2
    next
  end

  square = []
  j = 1
  while j * j < i
    square.push(j * j)
    j += 1
  end
  flag = true
  square.length.times do |k|
    if Prime.prime?(i - 2 * square[k]) && i - 2 * square[k] > 0
      flag = false
      break
    end
  end
  break if flag
  i += 2
end

p i