google recruit

!Ubuntu-20.04.1 !ruby-2.7.1p83

お題

テキストで読み込ませたe(自然対数の底)で連続する10桁の数のうち、最初の素数を求めよ

方針

やることはシンプルだ。文字列を読み込ませ、文字列を前から10桁ずつ切り出して素数かどうかを判定していく。

まず動くやつを作る

テキストを読み込む

まずは200桁までのeが記述されたテキスト(exp.txt)を作っておいて、それを読み込ませる。

def read_exp
  exp1=gets.to_s.chomp
end
exp1 = read_exp()

これでexp1に文字列が配列として読み込まれたようだ。試しに

puts exp1[0..9]

として、配列の0番目から9列目を出力させると

> ruby google_recruit.rb exp.txt
> 2.71828182
#+end_src ruby
あ、なるほど、2とかピリオドも配列に入ってるから、それを考慮してプログラムを書いていかないといけないな<br>
ちなみに僕は一つ上のディレクトリにいる状態で実行しようとしたら、ちゃんとexp.txtまでの相対パスを指定したのに「exp.txtなんてありません」とか言われてムカついて作業が3日止まりました。カレントディレクトリ基準で相対パスまで指定したのにそんなことある？と思ったけど謎
#+begin_src ruby
for i in 0..189
  num = exp1[2+i..11+i].to_i
    puts num
  end
end

初期値は配列の2～11番目を出力、以降それを190回繰り返して10桁ずつ取り出せる。実際に取り出してみるとちゃんと頭から10桁ずつ出力されてた。とりあえず10桁ずつ切り出すことはできたので、次はこれが素数であるかを判定していく

素数を判定する

素数の定義に従って、つまり自分の数字以外で2から順に割っていって、割り切れずに最後まで到達すればそいつが答えだ

def prime?(num)
  (2..num-1).each do |i|
    if num % i == 0
      puts i
      return false
    end
  end
  return true
end

each doで2から自分-1の数字まで順に割っていき、どこかで割り切れたタイミングがあればそこでfalse=素数じゃない判定を返す。全く割り切れずに終わったらtrueを返す。こういう関数を作っておいて、10桁の数字ごとに呼び出していくという地道な方法を取って、とりあえず動くものを作る

for i in 0..189
  num = exp1[2+i..11+i].to_i
  answer = prime?(num)

  if answer == true
    puts num
    break
  end
end

基礎的ではあるけど、exp1には文字列が格納されてるので、to_iを付けて整数にしないとprime?に渡したときに計算できなくて困ったことになる。僕はそれに気づくのに1時間かかって詰まりました。断続的に作業をしないと効率悪いって分かってんのに没頭しちゃうんだよねえ
あとはanswerにprime?の戻り値を入れて、それがtrue=素数であるなら表示するというだけ

> ruby google_recruit.rb exp.txt 
> 2.71828182

どうやら正解が導かれたらしい。
しかしこの2行の間には、実はとてつもなく長い時間が含まれている。時間がかかるのは分かってたけど、進行状況を出力しつつ動かしたら15分もかかりやがった。コンピュータの感覚で時間がかかるのかと思ったらマジモンの「時間がかかる」だった。
はっきり言って素数かどうかを判断するだけで「終了まで結構時間がかかりますのでその間にお茶でもどうぞ」状態では困る。なので高速化を試みる。

素数判定高速化事業

教科書によると高速化をするには。prime?のループの範囲を2..Math::sqrt(n).to_i+1とすると良いらしい

def prime?(num)
  (2..Math::sqrt(num).to_i+1).each do |i|
    if num % i == 0
      return false
    end
  end
  return true
end

これだけで今まで15分かかってたのが一瞬で答えが出るようになった。なんでやろなあ

たとえばnum=400だとしたらループ範囲は2..21となる。従来2..399だったのが平方根を取ることで約1/20になる。同様に

• 100000 : 2..317 -> 約0.3%
• 50000000 : 2..7072 -> 約0.1%
• 3000000000 : 2..54773 -> 約0.002%

という感じで、numが大きくなればなるほど短縮度合いは大きくなる。これによって大幅な高速化が可能になったと考えられる。
なお、ループ範囲がnumの平方根まででいい理由は、numはn×mとするとnもしくはmが必ずnumの平方根の切り上げ以下となるため。こういうことじゃないでしょうか？
というわけでgoogleは私に内定をください。もしくは給料だけをください。

参考記事

• Google recruit problem, exp and prime

---

• source ~/MasahiroOba/grad_members_20f/members/MasahiroOba/codes/../google_recruit.org