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 }