# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050
# 
# そのままだけど，重そうなので，i 番目から c 個の素数の総和を
# 1次元のIntegral Imageで算出する．
#
require 'prime'

module Pe50
  N = 1000000

  # IntegralImageを作成
  @@integral_image = [0]
  Prime.each(N).each_with_index do |prime, i|
    @@integral_image[i + 1] = @@integral_image[i] + prime
  end
  
  # i 番目から c 個の素数の総和
  def self.sum_prime(i, c)
    @@integral_image[i + c] - @@integral_image[i]
  end
  
  # 解答を取得
  def self.answer
    result = [0,   # 幅
              -1]  # 素数
    # N までの素数について j 番目から c 個の素数で自身が表せるか調べる．
    Prime.each(N).each_with_index do |prime, i|
      # 最大なのでこれまでの最大幅 +1 からスタート
      c = result[0] + 1
      while (sum_prime(0, c) < prime)
        0.upto(i) do |j|
          # j から c 個の素数の総和
          sum = sum_prime(j, c)
          if (sum > prime)
            break
          end
          if (sum == prime)
            # 一致したときの c が連続する幅
            result = [[c, sum], result].max
            break
          end
        end
        c = c.next
      end
    end
    result.pop
  end
end
puts Pe50.answer