Ruby - エラトステネスのふるい！

昨日は、エラトステネスのふるいの C++ によるアルゴリズムを紹介しました。

• C++ - エラトステネスのふるい！

今日は、同じアルゴリズムを Ruby で実現してみました。 アルゴリズム等については、昨日の記事等を参照してください。

以下、Ruby によるサンプルスクリプトです。

記録

0. 前提条件

• Cygwin 1.7.15
• Ruby 1.9.3-p194

1. Ruby スクリプト作成

今回作成した Ruby ソースは以下の通りです。 【 ファイル名： eratosthenes.rb 】

# -*- coding: utf-8 -*-
#=======================================
# エラトステネスのふるい
#=======================================
class Eratosthenes
  # 最大数
  NUM_MAX = 1000

  # 計算クラス
  class Calc
    # initializer
    def initialize
      # ふるいを全て 1 で初期化
      @ary_prime = Array.new( NUM_MAX + 1, 1 )
      # √NUM_MAX までチェックすればよい
      @int_limit = Math::sqrt( NUM_MAX ).to_i
    end

    # エラトステネスのふるい計算
    def calc_era
      # 2 以上 √NUM_MAX を超えない自然数までで判定すればよい
      2.upto( @int_limit ) do |i|
        # まだふるいに残っている数について処理
        if @ary_prime[i] == 1
          # 自分自身は素数になるから 2 * i 番目から
          ( 2 * i ).upto( NUM_MAX ) do |j|
            # i が j で割り切れれば古いから削除
            @ary_prime[j] = 0 if j % i == 0
          end
        end
      end
    end

    # コンソール出力
    def print_era
      puts "2 から #{NUM_MAX} までの素数："
      2.upto( NUM_MAX ) do |i|
        printf("%5d", i) if @ary_prime[i] == 1
      end
      printf( "\n" )
    end
  end

  # メイン処理
  begin
    # 計算インスタンス化
    obj_calc = Calc.new

    # エラトステネスのふるい計算
    obj_calc.calc_era

    # コンソール出力
    obj_calc.print_era
  rescue => e
    # エラーメッセージ
    puts "[例外発生] #{e}"
  end
end

2. 実行

実際に実行して素数を判定する。

$ ruby eratosthenes.rb
2 から 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

---

以上。