Googleの問題を解く
問題
「e(自然対数の底)の値で連続する10桁の数のうち、最初の素数」を求める。
- 素数判定
回答
def getNums()
line = readlines
len = line.length
num = ''
(0..len-1).each do |i|
num = num + line[i].chomp
end
return num
end
def prime?(num)
(2..Math.sqrt(num).to_i).each do |i|
if(num%i == 0)
return false
end
end
return true
end
digits = 10
if $PROGRAM_NAME == __FILE__
num = getNums().delete('.')
res = 0
(0..num.length-digits).each do |i|
res = num[i, digits].to_i
prime?(res) ? break : next
end
puts "e(自然対数の底)の値で連続する10桁の数のうち, 最初の素数は#{res}"
end
解説
- 問題が、外部ファイルに記述された e の数字を入力としていたので
getNums()で複数行の入力を結合するようになっています。が、まぁそこは気にせずに、数値の標準入力を受け取ります。
prime? の実装
require 'prime' によって Prime.prime?(n) が利用でき、高速に素数判定できますが面白く無いので今回は利用しません。自力で prime? を実装します。
def prime?(num)
(2..Math.sqrt(num).to_i).each do |i|
if(num%i == 0)
return false
end
end
return true
end
短っ!いや、もっと高速にするなら 偶数は弾く とかもあるけど、とりあえずこれでいいや。
- 理論的には、自分より低い数字で割り切れるかを見て、
trueorfalseを出力しているだけ。
(2..Math.sqrt(num).to_i).each do |i|
(2..Math.sqrt(num).to_i).each do |i| ここが重要な部分です。(2..num).each do |i| とするのが理論的ですが、これだと桁が多いときに処理が終わりません。いや、終わるけど時間がかかりすぎます。
Math.sqrt(num).to_i までの演算でいい理由
合成数(素数とは逆の意味) に関する性質$x$ が合成数ならば $\sqrt{x}$ 以下の約数を持つ
を利用しています。ですので、 num が合成数(=素数でない)なら
(2..Math.sqrt(num).to_i).each do |i|
if(num%i == 0)
return false
end
end
ここで引っかかって false を返します。逆に、ここをすり抜けた num は合成数でない(=素数)ので、 true を返します。
実行結果
- テキストファイルに e の値を記述します。
2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190
これをプログラムに渡してあげます。
$ ruby google_recruit.rb < in.txt
e(自然対数の底)の値で連続する10桁の数のうち, 最初の素数は7427466391
答えは 7427466391 である!
発展課題!?
この問題には続きというか、この問題の回答者だけに次の問題が用意されていたらしい。それが次の問題。
f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=__________
なるほどー。規則性を見つけるやつ。そして f(1)=7182818284 に見覚えがあった。
上の問題の e にこの数字あったやん f(2)=8182845904 これもあるやん。
解く
規則性を見つけましょう。
何桁目にあるか
小数第何位〜何位にその数が現れているかを探しましょう。
def getNums()
line = readlines
len = line.length
num = ''
(0..len-1).each do |i|
num = num + line[i].chomp
end
return num
end
if $PROGRAM_NAME == __FILE__
num = getNums().delete('.')
["7182818284", "8182845904", "8747135266", "7427466391"].each do |i|
pos = num.index(i)
puts "#{i} -> #{pos} ~ #{pos+(10-1)}"
end
end
こんなん作って
$ ruby google_recruit_find.rb < google_recruit_in.txt
7182818284 -> 1 ~ 10
8182845904 -> 5 ~ 14
8747135266 -> 23 ~ 32
7427466391 -> 99 ~ 108
さっぱりわからん。笑
テレビのクイズ問題にあるやつやろ
こういうのは大体、足したらいいねん
def getNums()
line = readlines
len = line.length
num = ''
(0..len-1).each do |i|
num = num + line[i].chomp
end
return num
end
if $PROGRAM_NAME == __FILE__
num = getNums().delete('.')
["7182818284", "8182845904", "8747135266", "7427466391"].each do |n|
sum = 0
(0..9).each do |i|
sum += n[i].to_i
end
puts "#{n} -> #{sum}"
end
end
こんなん作って
$ ruby google_recruit_sum.rb < google_recruit_in.txt
7182818284 -> 49
8182845904 -> 49
8747135266 -> 49
7427466391 -> 49
天才かもしれん (テレビの見過ぎ)
各桁の合計(10桁分)が49になる数字を e から探して5番目が答え。
回答
Ruby でこれを探すプログラムを書いて、回答を得る。
def getNums()
line = readlines
len = line.length
num = ''
(0..len-1).each do |i|
num = num + line[i].chomp
end
return num
end
digits = 10
if $PROGRAM_NAME == __FILE__
e = getNums().delete('.')
num = 0
(1..e.length-digits).each do |i|
sum = 0
(0..digits-1).each do |j|
sum += e[i, digits][j].to_i
break if sum > 49
end
puts "f(#{num = num.succ})=#{e[i, digits]}" if sum == 49
end
end
こんな感じ？？
$ ruby google_recruit2.rb < google_recruit_in.txt
f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=5966290435
f(6)=2952605956
答えは 5966290435 である!