RubyでProject Euler - Problem 46

Problem 46 (Project Euler) [原文]

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

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

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.

先に「平方数の2倍」の方から確定させていきます。「エラストテネスの篩」を二重に活用します。

コードは「続き」の欄に載せました。

  def prime_sieve(upper) # エラストテネスの篩
    sieve = Array.new(upper + 1,true)
    sieve[0] = sieve[1] = false
    2.upto(Math.sqrt(upper)) do |i|
      next unless sieve[i]
      (i + i).step(upper,i){ |j| sieve[j] = false }
    end
    sieve
  end

  limit = 100_0000
  p_sieve = prime_sieve(limit)
  ans = 0
  35.step(limit, 2) do |i|
    next if p_sieve[i] # 素数は対象外
    flag = true        # flagを立てておく
    (1..Math::sqrt(i/2)).each do |d| # 平方数の2倍をiから除外した値が
      if p_sieve[i - 2 * d ** 2]     # 素数で表せるのなら
        flag = false                 # flagを下ろして
        break                        # 内側のループ外へ脱出
      end
    end
    ans = i
    break if flag # flagが立っていたら外側のループ外へ脱出
  end
  puts ans # ansが解答

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。