Google Recruitを解く

はじめに

授業の課題で，rubyで問題を解くことになったので，
ruby初心者なりに調べながら書いてみた．

問題

「e(自然対数の底)の値で連続する10桁の数のうち，最初の素数」をrubyで解いてみる．

• 素数:1と自分自身以外の数で割り切れない自然数

ただし，eは200桁までとする

2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

プログラム

../codes/google_recruit.rb

def getfile()
      temps=readlines.map &:chomp
      temp=temps.join
      e=temp.delete('.')

      return e
end

def prime_judge(num)
      if num%2==0 then
          return false
      end

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

def main
      e=getfile()
      while e.length>=10 do
          num=e.slice(0, 10)
          if prime_judge(num.to_i) then
                  break
              end
          e.slice!(0)
      end
      puts "最初の素数は#{num}"
end

if $PROGRAM_NAME == __FILE__
      main
end

関数について簡単に

• getfile()
  • テキストから情報(e)を受け取る
• prime_judge(num)
  • numが素数ならtrue，さもなければfalseを返す
• main
  • 連続する10桁を取り出し，prime_judgeへ渡す
  • trueが返ってきたら表示

解説

getfile()

def getfile()
     temps=readlines.map &:chomp
     temp=temps.join
     e=temp.delete('.')

     return e
end

1. 改行をなくす
2. 配列の要素を文字列にする
3. 小数点消す

prime_judge(num)

def prime_judge(num)
     if num%2==0 then
         return false
     end

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

1. 偶数ならfalse
2. $\sqrt{num}$以下の整数で割り切れるならfalse
3. どちらでもなければtrue

さらに詳しく

まず，偶数かどうかの判断は終わっているので，奇数しか調べません．
合成数Nは1より大きく$\sqrt{n}$ 以下の約数を持つ を利用します．
合成数とは，1でも素数でもない数のことです．
つまり，合成数でないことを判断するために$\sqrt{n}$以下の奇数を順に調べていくことで素数判定を行うことができます．

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

main

def main
     e=getfile()
     while e.length>=10 do
         num=e.slice(0, 10)
         if prime_judge(num.to_i) then
                 break
             end
         e.slice!(0)
     end
     puts "最初の素数は#{num}"
end

1. getfileを呼び出して200桁のEをもらう
2. 先頭から10桁目までを取り出して，prime_judgeへ
3. trueEならbreakして表示，falseなら先頭を消す

結果

$ ruby google_recruit.rb < input.txt
最初の素数は7427466391

参考

• class String
• Ruby 複数行の入力を受け取る
• 配列の要素を連結して文字列化する
• プログラミング言語「Ruby」の記事まとめ
• 素数と合成数

---

• source ~/Desktop/grad_members_20f/members/mm-cell/post_org/google_recruit.org