12345678910111213141516171819202122232425262728293031 |
- #!/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
- }
- }
|