Project Euler 204
解法
ハミングDPする
実装(Ruby)
require 'prime' dp=Array.new p=Array.new TYPE=100 N=1000000000 Prime.each{|i| break if i>TYPE dp.push([0,i]); p.push(i) } ans=[1] loop do min=[] dp.each{|i| min.push(i[1]) } min=min.min break if min>N ans.push(min) dp.length.times{|i| if dp[i][1]==min dp[i][0]+=1 dp[i][1]=ans[dp[i][0]]*p[i] end } end p ans.size