EX2:Google Recruit

講義サイト

Google recruit problem, exp and prime

お題：数字の変換

自然対数の底eの値で連続する10桁の数のうち、最初に登場する素数を求める.
ただし、eは200桁までのみ使用する(それまでに出てくる).

2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190

これをテキストファイルに入れてプログラムから読み取る

実装例

def prime?(n)
  (2..Math::sqrt(n).to_i).each do |i|
   if n % i == 0
     false
     break
   end
   true
  end
end

exp = File.read('napier.txt').delete('.')
digit = 10

(0..exp.length).each do |i|
  slice_dig = exp.slice(i, digit).to_i
  if prime?(slice_dig)
    puts slice_dig
    break
  end
end

1～9行目が素数判定用メソッド prime?
2,3,…と少しずつ数を割っていく
割り切れたら素数じゃない、割り切れなかったら素数

11,12行目がファイルの読み取り.
e 200桁分は napier.txt に入れている.　小数点.は処理の邪魔なので削除.

14行目～最後の行がe分割用
200桁ある e を先頭から1つずつずらしながら切り抜いて素数判定を行う

ほぼ講義ページ通りに実装した

実行結果はこんな感じ.

7427466391

note

・素数判定を行うプログラム部分で、loopの範囲の記述を Math::sqrt(n).to_i+1 としている.
　(2..n-1).each do |i| とするよりも計算時間が早くなる. ループ回数が減るため、高速化する
　のは自明だが、どうして Math::sqrt(n).to_i+1 までのループでいいのかはよくわからなかった.
・ちなみに、この問題はGoogleのリクルート問題らしい.

---

• source ~/grad_members_20f/members/batamon-427/Google_Recruit.org