Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Problem 204

Project EulerProblem 204(日本語)です。
最初、以下のように作ってみました。これまでのProject Eulerの経験から分かることなのですが、例題(Type 5のハミング数で上限が10^8)は解けても、本問は時間がかかり過ぎて手におえません。

# -*- 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秒未満でした。