gistfile1.scala

package org.maximf

object P50 {
  def main(args: Array[String]) {
    println(go(1000000))
  }

  def go(limit: Long): Long = {
    val primes = Primes.below(limit).toArray
    val set = primes.toSet

    def find(index: Int, sum: Long): (Int, Long) = {
      if (sum > limit)
        (index - 1, sum - primes(index - 1))
      else
        find(index + 1, sum + primes(index))
    }

    var (count, sum) = find(0, 0)
    println(count, sum)
    var found = 0L

    def iter(index: Int, sum: Long): Long = {
      if (set(sum))
        sum
      else if (index + count == primes.length)
        0
      else {
        val s = sum - primes(index) + primes(index + count)
        if (s > limit)
          0
        else
          iter(index + 1, s)
      }
    }

    while (found == 0) {
      found = iter(0, sum)

      sum -= primes(count - 1)
      count -= 1
    }

    found
  }

}