課題

e(自然対数の底)の値で連続する10桁の数のうち，最初の素数をrubyで求めよ．（ただし，e(自然対数の底)は200桁までとする）

2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

まず，おおざっぱにプログラムを分割して考える．１．テキストからデータを読み込む．２．素数判定．３．連続する10桁の数を抽出，メイン関数

-1.テキストからデータを読み込む

def getdata()
      tmps=readlines.map(&:chomp)
      tmp=tmps.join
      e=tmp.delete('.')
      return e
end

mapメソッドは要素数分繰り返しブロックを実行．その戻り値を配列として返す．chompで改行を削除する処理を行う．その後は文字列に変換ののち，小数点を削除する．

-2.素数判定．

def judge(n)
      return false if n%2==0
      for i in 3...Math.sqrt(n) do
      return false if n%i==0
      i+=2
      end
      return true
end

まず，大前提として偶数は削除，今回は２については考慮しない．3以上の奇数に対して，以下の性質を利用．「合成数xはp≦√xを満たす素因子pをもつ」つまり,「合成数xはp≦√xを満たす素因子pをもつ」＝「xが合成数ならば、√x以下の約数を持つ」記の条件にかからないものを求める．

-3. 連続する10桁の数を抽出，メイン関数

def main
      data=getdata()
      while data.length>=10 do
        n=data.slice(0, 10)
        break if judge(n.to_i) 
        data.slice!(0)
      end
      puts "A.#{n}"
end

200桁の自然対数の底を受け取り，連続する10桁の数を受け取り，判定する．

実行すると，

$ ruby google.rb < e.txt
A.7427466391

*参考 -素数判定

source ~/grad_members_20f/members/szksjm/qiita_post/google.org

google recruit

課題