« "math_tool.rb" by Ruby 1.9.1 | トップページ | 素因数分解 »

2009年5月25日 (月)

「1以上100未満の『2個の素数の積』である整数を列挙しなさい」

先日、あるブログで「1以上100未満の『2個の素数の積』である整数を列挙しなさい」という問題を Python で解いているのをみました。

ちょっと簡単な "Project Euler" みたいな感じなので、私も Ruby で解いてみようと思ったわけです。


一番簡単なのは、100 未満の素数を順に掛け合わせていって、100 未満の数だけ集める方法ですが、これだと計算に多くの無駄があったり、答に重複が出るので、もう少し考える必要があります。


まず重複をなくすために、二つの素数を a, b としたときに必ず a ≦ b になるように決めます。

次に、a と b の範囲を考えます。

a ≦ b かつ a × b < 100 ですから、a は 10 未満になることが分かります。

また、b は a ≦ b < 100 / a の範囲になります。ただ、毎回 b の範囲を計算し直すのも時間の無駄のような気がしたので、これに関してはちょっと方法を変えてみました。


Ruby で素数を扱う場合、一番手っ取り早いのは 1.9 についてくる "mathn" "prime.rb" に含まれる Prime クラスを使うことだと思います。

require 'prime' include Math Limit = 100 ans = Array.new a = Prime.instance b = Prime.instance a.each(sqrt(Limit).to_i) do |i| b.each do |j| next if j < i c = i * j if c < Limit then ans.push(c) else break end end end p ans.sort
=> [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] real 0m0.086s user 0m0.044s sys 0m0.008s

この方法でも結構速いのですが、今回のように使う素数列の上限が決まっている場合、前回紹介した "prime_list" メソッドの方が若干速かったりします。


この "prime_list" は、Ruby のサンプルに含まれている "sieve.rb" を独自に改良したものです。

"sieve.rb" はいわゆる「エラトステネスの篩」なのですが、一般的なものが割り算の余りを評価して合成数を除外していくのに対して、"sieve.rb" は足し算を使うことによって合成数を除外していきます。

アセンブラを知っている方はご存知と思いますが、コンピュータは足し算や引き算は得意ですが、掛け算や割り算はあまり得意ではありません。

したがって割り算を多用するコードより足し算を多用するコードのほうが速く処理できます。

私が "sieve.rb" を改良してつくった "prime_list" は最初から偶数を除外しておくなどの工夫を加えてあります。

Ruby 1.9 なら百万以下の素数列を 0.5 秒ほどでつくってしまいます。

include Math def prime_list(n) return [] if n <= 1 size = n / 2 - 1 max = sqrt(n).to_i a = Array.new(size){|i| 2 * i + 3} a.unshift(nil) max.times do |i| j = a[i] next unless j (2 * i * (i + 1)).step(size, j) do |k| a[k] = nil end end return a.unshift(2).compact end Limit = 100 p_lst1 = prime_list(sqrt(Limit).to_i) p_lst2 = prime_list(Limit / 2) ans = Array.new p_lst1.each do |a| p_lst2.each do |b| next if a > b c = a * b if c < Limit then ans.push(c) else break end end end p ans.sort
=> [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95] real 0m0.084s user 0m0.024s sys 0m0.020s

« "math_tool.rb" by Ruby 1.9.1 | トップページ | 素因数分解 »

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45124769

この記事へのトラックバック一覧です: 「1以上100未満の『2個の素数の積』である整数を列挙しなさい」:

« "math_tool.rb" by Ruby 1.9.1 | トップページ | 素因数分解 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ