RubyでProject Euler - Problem 50

Problem 50 (Project Euler) [原文]

素数41は6つの連続する素数の和として表せる:

41 = 2 + 3 + 5 + 7 + 11 + 13.

100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

2を先頭要素とする素数配列:$p_listとします。$p_listの先頭要素から順次各要素を加算して求められる部分和が初めて100万を超えるときの要素のインデックスは546です。

従って、題意の項数を目一杯大きく見積もっても547個であり、実際にはこれ以下の項数でしか表せないことがわかります。

ですから、この項数を順次減らすとともに加算の起点となる素数をずらすことで、題意の素数を探索していくという方針にしました。

また、項数は必ず奇数であることに注意します。これを忘れるとどえらいことになります(笑)

Level 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

  def prime_list(upper) # エラストテネスの篩から素数配列作成
    return [] if upper < 2
    primes=Array.new
    prime_sieve(upper).each_with_index{ |isPrime,i| primes.push i if isPrime }
    primes
  end

  begin_time = Time.now

  limit = 100_0000
  $p_list = prime_list(limit)

  s, record = 0, 0 # s:部分和, record:部分和の要素数

  # recordの初期値決定
  while s < 100_0000
    s += $p_list[record]
    record += 1
  end
  record += 1 if record % 2 == 0   # 奇数にしておく
  
  # 真のrecordを探索
  loop do
    s, i = 0, 0 # s:部分和, i:部分和の初項インデックス
    while (s = $p_list[i..(i+record-1)].inject(0){|u,v|u+v}) < 100_0000
      if $p_list.include?(s) # 部分和:sが素数であるか
        thats_all = true     # 探索完了
        break
      else
        i += 1               # 初項の位置をずらす
        thats_all = false    # 探索失敗
      end
    end
    if thats_all
      puts "Ans : #{s} - #{record}個, 初項 #{$p_list[i]}"
      puts " -- #{Time.now - begin_time}sec"
      exit
    end
    record -= 2 # recordを減算してリトライ
  end

ご注意

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

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

コメントはありません。

ご注意

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