RubyでGoogleの問題を解く


# Googleの問題を解く


## 問題

「e(自然対数の底)の値で連続する10桁の数のうち、最初の素数」を求める。

-   素数判定


## 回答

```ruby
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?` を実装します。

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

短っ!いや、もっと高速にするなら **偶数は弾く** とかもあるけど、とりあえずこれでいいや。

-   理論的には、自分より低い数字で割り切れるかを見て、 `true` or `false` を出力しているだけ。


#### (2..Math.sqrt(num).to\_i).each do |i|

`(2..Math.sqrt(num).to_i).each do |i|` ここが重要な部分です。<br>`(2..num).each do |i|` とするのが理論的ですが、これだと桁が多いときに処理が終わりません。いや、終わるけど時間がかかりすぎます。


#### Math.sqrt(num).to\_i までの演算でいい理由

合成数(素数とは逆の意味) に関する性質$x$ が合成数ならば $\sqrt{x}$ 以下の約数を持つ<br>を利用しています。ですので、 `num` が合成数(=素数でない)なら

```ruby
(2..Math.sqrt(num).to_i).each do |i|
  if(num%i == 0)
    return false
  end
end
```

ここで引っかかって `false` を返します。逆に、ここをすり抜けた `num` は合成数でない(=素数)ので、 `true` を返します。


## 実行結果

-   テキストファイルに e の値を記述します。

```text
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` に見覚えがあった。<br>**上の問題の e にこの数字あったやん** <br>`f(2)=8182845904` これもあるやん。


### 解く

規則性を見つけましょう。


#### 何桁目にあるか

小数第何位〜何位にその数が現れているかを探しましょう。

```ruby
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

さっぱりわからん。笑


#### テレビのクイズ問題にあるやつやろ

**こういうのは大体、足したらいいねん** <br>

```ruby
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

**天才かもしれん** (テレビの見過ぎ)<br>各桁の合計(10桁分)が49になる数字を e から探して5番目が答え。


### 回答

Ruby でこれを探すプログラムを書いて、回答を得る。

```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` である!



------