Project EulerのProblem 204(日本語)です。
最初、以下のように作ってみました。これまでのProject Eulerの経験から分かることなのですが、例題(Type 5のハミング数で上限が)は解けても、本問は時間がかかり過ぎて手におえません。
# -*- coding: utf-8 -*- require 'prime' TYPE = 100 LIMIT = 1_000_000_000 primes = Prime.each(TYPE).to_a hamming = Array.new(LIMIT+1, false) hamming[1] = true [*1..LIMIT].each {|i| if hamming[i] primes.each {|p| v = p * i hamming[v] = true if v <= LIMIT } end } p hamming.select{|v| v }.size
204.rb
Project Euler 204 - 桃の天然水を参考にさせていただきました。なるほどと思うのですが、なかなか自分では再帰構造を見出してプログラミングするレベルまでいけません。実行時間も1秒未満でした。