project-euler/Sidef/077 Prime summations.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Website: https://github.com/trizen

# What is the first value which can be written as the sum of primes in over five thousand different ways?

# https://projecteuler.net/problem=77

# Runtime: 1.755s

var primes = []

func count(n, i=0, sum=0) is cached {
    return 1 if (sum == n)
    return 0 if (sum > n)
    return 0 if (i > primes.end)

    count(n, i+1, sum) +
    count(n, i, sum + primes[i])
}

for i in (4 .. 1e6) {
    primes = (i-2).primes
    if (count(i) > 5000) {
        say i
        break
    }
}