require'prime' n=gets.to_i dp=[-1]*-~n dp[0]=0 Prime.each(999){|p| (n-p).downto(0){|i| dp[i+p]=dp[i]+1 if dp[i]>=0 and dp[i+p]