furui = {} primes = {} -- get primes n = io.read("*n") hn = math.ceil(n / 2) for i = 2, hn do if(not furui[i]) then table.insert(primes, i) jmax = math.floor(hn / i) for j = 2, jmax do furui[j * i] = true end end end -- do DP sumbox = {} cursum = 0 sumbox[0] = 0 -- for i = 1, n do sumbox[i] = -1 end for k, v in pairs(primes) do for i_sum = cursum, 0, -1 do if(sumbox[i_sum] ~= nil) then if(sumbox[i_sum + v] == nil) then sumbox[i_sum + v] = sumbox[i_sum] + 1 else sumbox[i_sum + v] = math.max(sumbox[i_sum] + 1, sumbox[i_sum + v]) end end end cursum = math.min(n, cursum + v) end if(sumbox[n] == nil) then print("-1") else print(sumbox[n]) end