Skip to content

Instantly share code, notes, and snippets.

@burnall
Created February 20, 2015 08:35
Show Gist options
  • Save burnall/1ab7fe916db7a3b566b4 to your computer and use it in GitHub Desktop.
Save burnall/1ab7fe916db7a3b566b4 to your computer and use it in GitHub Desktop.
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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment