Problem 77

Problem 77 - Project Euler
分割数の様な問題。ただし支払いに使えるコインの額面は素数であると。
26秒かかった。
再帰を使った。答がすぐに出たからよかったけど、こういう計算はRだとやっぱり時間かかる。

limit <- 10^5
sieve <- logical(limit)
sieve[1] <- TRUE
sieve[seq(4,limit,2)] <- TRUE
for(i in 3:sqrt(limit)){
  if(!sieve[i]){
    for(j in seq(2*i,limit,i)){
      sieve[j] <- TRUE
    }
  }
}
prms <- (1:limit)[!sieve]

ways <- function(n,i=1){
  if(n-prms[i]==0) return(1)
  if(n-prms[i]<0) return(0)
  return(ways(n-prms[i],i) + ways(n,i+1))
}

ans <- 1
repeat{
  if(ways(ans)>5000) break
  ans <- ans+1
}