Google recruit problem, exp and prime

Google Recruit

{e(自然対数の底)の値で連続する10桁の数のうち，最初の素数}

をrubyで求めよ．ただし，e(自然対数の底)は200桁までで

2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190

である．これをテキストにコピーして読みこませよ．

解説

グーグル、謎の人材募集広告–シリコンバレーのビルボードに　

Stefanie Olsen (CNET News.com) 2004/07/12 08:40

先週、シリコンバレーの中心を走るハイウェー101沿いのビルボードに、複雑な数学の問題を載せた広告が現れた。

(中略)この広告には、「｛eの値中の、最初の連続する10桁の素数｝.com」("{first 10 digit prime found in consecutive digits e}.com." )と書かれている。この答えの「7427466391.com」にアクセスすると、そのウェブページにはさらに別の問題(下記参照)が用意されているが、ここにもGoogleが関与していることを示すものは全くない。 この問題を解くと、Googleの研究開発部門「Google Labs」へのページに辿りつく。このページには、「Googleの構築を通して我々が学んだことの1つに、自分が何かを探しているとき、向こうも自分を探している場合のほうが見つかりやすいということがある。我々が探しているのは、世界最高のエンジニアであり、あなたこそその人なのだ」と書かれている。

解法

各個撃破で解いて行きましょう．おおまかな流れは，

1. 素数判定
2. eの値中の、連続する10桁の数
   1. 数の読み込み
   2. 10桁の整数の生成
3. 最初の連続する10桁の素数を探す

です．

素数判定

素数判定を原理から実現せよ．ある数nが素数かどうかは，

自分自身の数nと1以外の数で割りきれないかどうか                                                                      

で判定される．

1. 割り算の余り(剰余)は%で求まる．
2. [*2..n-1].each do |i|でnを次々と割っていき，
3. 割り切れたところでループをbreak．
4. 適当にたてた番兵（変数名warden）を見てloopが最後までまわっているかどうかで，
5. 素数(prime number)かどうかを判定すればよい.

メソッド化:prime?

前節で求めた素数判定プログラムをmethodにせよ．test部は

require "./assert_equal_final"
expected = [2,3,5,7]
results = []
[*2..10].each do |num|
  results << num  if prime?(num)
end

assert_equal(expected, results)

つまり関数prime?は，素数ならtrue, 素数でなければfalseを返す．

exp.txtの読み込み:read_exp

テキストの読み込みは，

def read_exp
  exp1=gets.to_s.chomp
end
exp1 = read_exp()
assert_equal('2.71828182', exp1[0..9])

[BobsNewPBG4-6:~/Ruby/google] bob% ruby google.rb < exp.txt
expected :: 2.71828182
result   :: 2.71828182
succeeded in assert_equal.

exp.txtの内容を"<"で読み込ませている．

文字から数字の生成

文字列exp1を配列とみなして exp1[0] などで表示．

exp1=gets.to_s.chomp
puts exp1
puts exp1[0]
assert_equal('7182818284', exp1[2..2+10-1])

puts exp1[2..2+10-1].to_i

[BobsNewPBG4-6:~/Ruby/google] bob% ruby google2.rb < exp.txt
2.71828182845904523536028747135266...
2
7182818284

もっとも簡単には最後のputs exp1[3..12].to_i でいいが，これは後の問題でつかえないのでもうすこしちまちま作る．

素数判定の高速化

素数判定programのloopの範囲 2..i_max において， i_max=n-1 ではなく，i_max=Math::sqrt(n).to_i+1 にすれば高速化される．なぜか考えよ．

time ruby google_recruit.rb < exp.txt
[100, 7427466391, true]
[124, 7413596629, true]
[150, 6059563073, true]
[172, 3490763233, true]
[183, 2988075319, true]

________________________________________________________
Executed in  632.32 millis    fish           external 
   usr time  492.65 millis  241.00 micros  492.41 millis 
   sys time  121.71 millis  576.00 micros  121.14 millis 

上の方で作った，2..n-1のloopでは終わらない．

• @scivolaさんの指摘で修正．<2020-11-28 Sat>

類題(最終課題)

Congratulations. You've made it to level 2. Go to www.Linux.org and enter Bobsyouruncle as the login and the answer to this equation as the password.

f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=__________

---

• source ~/git_hub/ruby_docs/chart_style_ruby/tdd_google_recruit/google_recruit.org