Ruby - 素数判定!

Updated:


昨日は、任意の自然数が素数か否かを判定する C++ によるアルゴリズムを紹介しました。

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

ただ、Ruby には Prime クラスというものが用意されているので、実際には自分で判定する必要もありません。 今回は自分で判定した結果が正しいかを確認する意味も含めて、Prime クラスで判定した結果も確認できるようにしました。 ※Prime クラスは Ruby 1.8 までは mathn で定義されていました。現在はライブラリ prime に移動しています。

【2017-11-19 追記】
素数判定について再考しました。
こちら」の方をご参照ください。
【追記ここまで】

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

記録

0. 前提条件

  • Cygwin 1.7.15
  • Ruby 1.9.3-p194

1. Ruby スクリプト作成

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

# -*- coding: utf-8 -*-
require 'prime'

class PrimeNumber
  # 素数クラス
  class PrimeNum
    # 素数判定
    def is_prime(a)
      return false if a == 1  # 1 は素数でない
      return true  if a == 2  # 2 は素数
      return true  if a == 3  # 3 は素数

      # 2 から √a を超えない整数までループ処理
      int_limit = Math::sqrt(a).to_i
      flag = false
      2.upto( int_limit ) do |i|
        # 途中割り切れたらフラグを立ててブレーク
        if a % i == 0
          flag = true
          break
        end
      end

      # 最後まで割り切れなかったら素数と判定
      return !flag
    end
  end

  # メイン処理
  begin
    # 素数クラスインスタンス化
    obj_prime = PrimeNum.new

    while true
      # データ入力
      print "自然数 ( 0 : 終了 ):"
      int_num = gets.chomp.to_i
      break if int_num < 1

      # 自作素数クラスによる判定
      str_0 = obj_prime.is_prime(int_num) ? "素数" : "素数でない"
      puts "#{int_num} : #{str_0}"

      # Prime クラスによる判定
      str_1 = Prime.instance.prime?(int_num) ? "素数" : "素数でない"
      puts "[ Prime クラス : #{str_1} ]"
    end
  rescue => e
    # エラーメッセージ
    puts "[例外発生] #{e}"
  end
end

2. 実行

実際に実行して最大公約数を計算する。

$ ruby prime_number.rb
自然数 ( 0 : 終了 ):4
4 : 素数でない
[ Prime クラス : 素数でない ]
自然数 ( 0 : 終了 ):7
7 : 素数
[ Prime クラス : 素数 ]
自然数 ( 0 : 終了 ):95867461
95867461 : 素数
[ Prime クラス : 素数 ]

参考サイト


以上。





 

Sponsored Link

 

Comments