Project Euler 200

プログラミング

色々飛ばして一気に200問目。


2, 5 の倍数以外は、耐素数性はないと仮定して解いた。

手順はこれ。

  • q = 2 と固定して、条件を満たす sqube を小さいものから200個リストアップする。
  • 次に q = 5 と固定して、リストアップ済みの sqube の最大値以下でかつ、条件を満たす sqube をリストアップする。
  • 次に p = 2 or 5 と固定して、同様に条件を満たす sqube をリストアップする。
  • これまでにリストアップした sqube をソートして、200番目の sqube を求める。（これまでにリストアップされたsqubeは243個だった）


この実行時間は 10秒 (Ruby 1.9.1 使用)
sqube 生成に使った素数は 10**6 以下の素数。(この数字は実験して最小のものを求めた)


ただ、この解法に辿り着くまでにはすごく時間がかかった。
というのも、「2, 5 の倍数以外は、耐素数性はない」という仮定をせずに愚直に解こうとしていたから、時間もメモリも使いまくって終わらないとか、工夫しようとするとやけにコードが難しくなり破綻したりしていた。


まあ、とりあえずなんとか解くことができてよかったよ。。

ちなみに、私は551人目の解答者のようです。Good!


なお、今回の問題を解いているときに、今までに使っていた素数を求めるコードは実は遅いことに気づいた。(delete_ifを多用するのはまずい）

今までのコード

def primes_old(maxnum)
  return [2] if maxnum == 2

  prime = 3.step(maxnum, 2).to_a

  (3..(Math.sqrt(maxnum).to_i)).each do |f|
    prime.delete_if {|t| t!=f && t%f == 0}
  end

  [2] + prime
end

修正したコード

def primes(maxnum)
  ary = (2..maxnum).to_a

  (2..(Math.sqrt(maxnum).to_i)).each do |num|
    (num*2).step(maxnum, num).each do |t|
      ary[t-2] = nil
    end
  end
  ary.delete_if {|t| t.nil?}
  ary
end

時間差は、10**6の引数で、それぞれ 20s, 6s


＜補足＞
2, 5 の倍数以外は、耐素数性はないと仮定したと書いたが、記事を書いた後にProblem 200のポストをちょいちょい見ていたら、実は2,5の倍数以外でも、"200"を含んで耐素数性を持つものが存在するらしいことが分かった。

105200812888979987 = 2011^2 * 2963^3

というか、みんなすごいですね。。