はじめに
今回は以下の記事の「Google Recruit」及び「類題(最終課題)」を解くコードをRubyで実装する．
Google Recruit
$e$(自然対数の底)の値で連続する10桁の数のうち，最初の素数を出力せよ．ただし，$e$は以下の数とする．
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190
入力
まず上記の$e$の値を標準入力から読み込む．
google_recruit.rb
exp = gets.to_s.chomp
exp = exp[0] + exp[2...exp.length]
素数判定
次に，与えられた自然数$n$が素数かどうかを判定する関数is_primeを実装する．$a \times b = n$ となる自然数 $a, b$ について $\sqrt{n} < a$ ならば $b < \sqrt{n}$ が成り立つので，2から$\sqrt{n}$までの自然数で$n$が割り切れるか試すことで，$n$が素数かどうか判定できる．計算量は$O(\sqrt{n})$．
google_recruit.rb
def is_prime(n)
for i in 2..n do
if n < i*i
break
end
if n % i == 0
return false
end
end
return n != 1
end
答えを出力する
文字列から連続する10桁を切り出し，素数判定をすることで問題の答えを出力する．
google_recruit.rb
for i in 0...exp.length - 10 do
if exp[i] == '0'
next
end
n = exp[i...i+10].to_i
if is_prime(n)
puts n
break
end
end
答え
上記のプログラムを実行した結果，答えは7427466391であった．
類題(最終課題)
以下のf(5)を求めよ．
f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=__________
考察
先ほど与えられた$e$に含まれる10桁で，数字和が49であるものが前から順にf(1), f(2), … となっていることが(問題をそのままgoogle検索にかけることで)分かる．よって5番目に表れるそのような10桁を見つけるプログラムを書く．
プログラム
文字列から連続する10桁を切り出し，数字和が49であるかどうか判定し，そのうち前から5番目のものを出力する．
google_recruit_final.rb
exp = gets.to_s.chomp
exp = exp[0] + exp[2...exp.length]
cnt = 0
for i in 0...exp.length - 10 do
digit_sum = 0
for j in 0...10 do
digit_sum += exp[i + j].to_i
end
if digit_sum == 49
cnt += 1
end
if cnt == 5
puts exp[i...i+10]
break
end
end
答え
上記のプログラムを実行した結果，答えは5966290435であった．
- source ~/grad_members_20f/members/ryuta-kikuchi/qiita_articles/google_recruit.org