Google Recruit

はじめに

今回は以下の記事の「Google Recruit」及び「類題(最終課題)」を解くコードをRubyで実装する．
- Google recruit problem, exp and prime

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