トップ > Ruby > エラトステネスの篩（Ruby）

エラトステネスの篩（Ruby）

Ruby 数学

「エラトステネスの篩」で、素数を求めてみます。Ruby でやってみました。

極めて素直にコードを書いてみました。難しいことは何もないと思います。もう少し Ruby らしく書くこともできるでしょう。
eratosthenes.rb

def set_f(i, max)    #素数でない数にフラグを立てる
  for j in 2..(Math.sqrt(max).to_i)
    $a[i * j] = 2
  end
end

max = (ARGV[0] || 100).to_i
$a = Array.new(max)

for i in 2..max
  if $a[i] != 2 
    $a[i] = 1     #iは素数
    set_f(i, max)
  end
end

for i in 2..max
  print i, "  " if $a[i] == 1
end

結果

>ruby eratosthenes.rb 1000
2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73
79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163
167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251
257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349
353  359  367  373  379  383  389  397  401  409  419  421  431  433  439  443
449  457  461  463  467  479  487  491  499  503  509  521  523  541  547  557
563  569  571  577  587  593  599  601  607  613  617  619  631  641  643  647
653  659  661  673  677  683  691  701  709  719  727  733  739  743  751  757
761  769  773  787  797  809  811  821  823  827  829  839  853  857  859  863
877  881  883  887  907  911  919  929  937  941  947  953  967  971  977  983
991  997


1000万以下くらいの素数なら、充分速く求められると思います。
上のコードの最終 3行を以下のように替えれば、最大の素数だけ表示します。（無駄なループが殆どなので、改善の余地が大いにあります。）

for i in 2..max
  n = i if $a[i] == 1
end
puts n

結果

>ruby eratosthenes.rb 10000000
9999991


最後を、こんな風に改善できるかな。結果は同じですが。

while $a[max] == 2 do
  max -= 1
end
puts max

1000万以下の最大の素数を求めるのの、ベンチマークをやってみました。結果は

      user     system      total        real
  6.536000   0.032000   6.568000 (  6.601378)

だいたい 6.54秒ということですか。改善前より 1.2秒ほど速くなります。Benchmark モジュールを使ったのですが、何度もやると、多少のブレが出るのはどうしてなのだろう。まあ極めて微小な差ですが。
　
　
※追記（2017/6/16）
いまならこうも書くでしょう。Ruby は記述力が高くて楽しいですな。

def eratosthenes(n)
  ar = (0..n).to_a
  2.upto(Math.sqrt(n).to_i) do |i|
    next if ar[i].zero?
    2.upto(n / i) {|j| ar[i * j] = 0}
  end
  ar[2..-1].reject {|x| x.zero?}
end

p eratosthenes(1000)

　
ベンチマークしてみました。（2017/7/27）

require 'benchmark'

Benchmark.bm do |x|
  x.report {eratosthenes(1000_0000)}
end

結果。

       user     system      total        real
   3.000000   0.010000   3.010000 (  3.009530)

1000万以下の素数で、3秒ほどですか。以前の結果よりも速いですね。半分くらいの時間で済んでいますか。


※再追記（2017/10/16）
Ruby FFI を使って求めてみました。


※再々追記（2018/10/12）
こんなスマートな求め方もあります。関数型プログラミングっぽいですね。ただし、時間もすごくかかりますし、ちょっと大きい数を入れるとスタックオーバーフローします。

def sieve(x, *xs)
  ys = xs.reject {|y| (y % x).zero?}
  [x] + (ys.empty? ? [] : sieve(*ys))
end

p sieve(*(2..50))
#=>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

　

※再々々追記(2022/1/8)

def eratosthenes(n)
  sieve = [*0..n]
  sieve[0] = sieve[1] = nil
  
  (2..Integer.sqrt(n)).each do |i|
    next unless sieve[i]
    (i * i).step(n, i) { sieve[_1] = nil }
  end
  sieve.compact
end

p eratosthenes(1000)