素数列挙 Ruby

質問

1000までの素数を列挙するプログラムは書けました。
def s(max)
arr=(2..max).to_a
(2..Math::sqrt(max)).each do |i|
arr.delete_if {|a|a % i == 0 && a!=i}
end
arr
end

puts s(1000)

今度は10の10乗から10の11乗の間に存在する素数を列挙するプログラムを書きたいのです。
時間は気にしないので、上の試し割り方法で良いです。助けてください。
また、メモリの上限を変更する必要がありますか？ないとしたら、どの範囲から変更は必要ですか。
10の20乗から？30乗から？
本当の初心者なのでどうかよろしくお願いします。

回答No.4

tatsu99

>これはミラー・ラビン法でしょうか？ここで使われている素数判定法の中身をご存じでしたら教えてください。

素数のクラスの使用するためには
require 'prime'
が必須です。
このprimeの中身が、あなたの求めているソースになります。
私の環境で（windows7)にrubyをインストールした場合、
（c:\Rubyにインストールしました。）
（rubyのバージョンは1.9.3p374 (2013-01-15) [i386-mingw32]）
C:\Ruby\lib\ruby\1.9.1\prime.rb
に、素数クラスのソースがあります。
あなたの環境の詳細は、不明ですが
prime.rbがソースになりますので、
libの下を検索すれば見つかる筈です。

回答No.3

tatsu99

>今度は10の10乗から10の11乗の間に存在する素数を列挙するプログラムを書きたいのです。
回答は、あなたが、本当に求めているのが何かによります。
１．もし、素数そのものの結果だけ（方法は何でも良い）がほしいなら、
以下のプログラムを実行してください。（素数を扱うクラスがあるのでそれを利用する）
-----------------------------------------------------
require "prime"
def primes(sval,eval)
sval.upto(eval) do |i|
p i if i.prime?
end
end
primes(10**10,10**11)

-----------------------------------------------------
２．今、実行されているやり方で、結果がほしいというであれば、
#1の方が言われているように、「メモリサイズが足りませんので、現実的には不可能である」が、
回答になります。
３．１のような結果だけでなく、素数の求め方のアルゴリズムまで含めて自分で納得できる方法が
ほしい、ということであれば、以下のやり方を１つの例としてあげておきます。
（アルゴリズム的にはかなり手抜きですが、メモリを消費しないで素数を算出する例と考えてください）
---------------------------------------------------
def prime?(val)
maxv = Math::sqrt(val).truncate
(2..maxv).each do |i|
return false if val % i == 0
end
return true
end
def primes(sval,eval)
sval.upto(eval) do |i|
p i if prime?(i)
end
end
primes(10**10,10**11)

---------------------------------------------------
primes(sval,eval)は、sval～evalの範囲の素数を印字します。
prime?(val)は、valが素数ならtrueを返し、そうでないならfalseを返します。

以下、１と３の実行結果です。（10**10～10**10+100）までの実行結果です。
primes(10**10,10**11)は
primes(10**10,10**10+100)
で実行しています。
primes(10**10,10**11)を実際には実施していません。
1時間ほど実施しましたが、終了しませんでしたので、終了するまでの正確な時間は判りません。
ご了承ください。
実行結果
10000000019
10000000033
10000000061
10000000069
10000000097

補足

どうもありがとうございました。1で教えていただいたプログラムがまさに求めていたものでした。試し割り法ではここまで早くできませんね。これはミラー・ラビン法でしょうか？ここで使われている素数判定法の中身をご存じでしたら教えてください。

回答No.2

ki073

eachループの中に
puts i
でも入れておけばいかがでしょうか。
arrが表示できる範囲でしたら
p arr
でも

回答No.1

ki073

上限と下限を指定できるように書きかえてみました。
def s(range)
arr=range.to_a
(2..Math.sqrt(range.last)).each do |i|
arr.delete_if {|a|a % i == 0 && a!=i}
end
arr
end

puts s(2..1000)

メモリ容量を無視すれば
puts s(10**10..10**11)
で計算可能です。
しかし、（計算間違いが無ければ）配列を確保するだけで1TB程度必要ですので、とても計算できません。範囲を狭めて計算する必要が有ります。
((10**11-10**10)*8+α)Bytes必要

>メモリの上限を変更する必要がありますか？
Ruby自体は使用メモリ量は設定できず、仮想記憶を含めた上限まで使えるはずです。
仮想記憶を使いだすとものずごく遅くなりますが。

補足

どうもありがとうございました。教えていただいた方法は数値の範囲を大きくすると、大きくした分だけ時間をかけてから、画面に表示されますね。
プログラムの途中経過を画面表示されるように設定するにはどうしたらいいか、またぜひ教えていただけませんか？