トップ > Ruby > プロジェクト・オイラーで遊ぶ（Ruby）

プロジェクト・オイラーで遊ぶ（Ruby）

Ruby 数学 アルゴリズム・パズル

Project Euler - PukiWiki
プロジェクト・オイラーというのは、数学の問題をプログラムで解いてみようというものです。全部解こうとか、そういう殊勝な決意ではないのですが、ちょっとだけ Ruby で遊んでみました。結果は保証の限りではありません。

（問１）
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

counter = 0
for i in 3...1000
  counter += i if (i % 3).zero? or (i % 5).zero?
end
puts counter


（問２）
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

a = 1; b = 2
counter = 2
loop do
  a, b = b, a + b
  break if b > 400_0000
  counter += b if b.even?
end
puts counter


（問３）
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.

N = 600851475143; n = N
i = 2
ar = [1]
loop do
  if (n % i).zero?
    n /= i
    ar.push(i)
    break if ar.inject(:*) == N
  else
    i += 1
  end
end
puts ar[-1]

実質的に素因数分解をやっています。行列 ar に素因数が入っています。ただし ar[0] に余分な数値 1 が入っているので、これを取り除いた上でですが。

（問４）
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

def check(num)
  nums = num.to_s
  for i in 0...(num / 2.0)
    return false if nums[i] != nums[-i - 1]
  end
  true
end

ans = []
999.downto(100) do |i|
  i.downto(100) {|j| ans.push(i * j) if check(i * j)}
end
puts ans.max

このあたりから高速化が問題になってきますね。自分のコードでは特に高速化を考えていないので、結構時間がかかります。このやり方だと、最初にヒットした数値が、最大であるという保証がありません。なので、すべて求めてその中の最大値という、工夫のない方法になってしまっています。自分の環境で 29秒ほどかかりました。しかし、馬鹿正直にすべて求めなくとも、だいたい 900以上の 2数の積だろうというのは予想がつくわけですね。なので downto() の中の数字を二箇所とも 900 にすれば、答えは瞬殺（1秒未満）で求められます。仮にこれで求まらなければ、下限を 800とかにしてやればいいわけです。ちなみに 906609 = 993 * 913 です。
　※追記　String#reverse メソッドを見つけました。0.2秒以内ほどに短縮できました。（12/12）

ans = []
999.downto(100) do |i|
  i.downto(100) {|j| ans.push(i * j) if (a = i * j).to_s == a.to_s.reverse}
end
puts ans.max


（問５）
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

def check(num)
  for i in 2..20
    return false unless (num % i).zero?
  end
  true
end

i = 1
until check(i)
  i += 1
end
puts i

これも高速化が問題なのでしょうね。自分のはあまりにも素朴な方法なので、1〜10 までは一瞬だからと思ってやると、相当に時間がかかります（自分の環境で 69秒ほど）。ちょっと思いついて 2行目を 20.downto(2) do |i| に替えたところ、多少改善されて 50秒ほどになりました。

（問６）
最初の10個の自然数について, その二乗の和は,
1^2 + 2^2 + ... + 10^2 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)^2 = 3025
これらの数の差は 3025 - 385 = 2640 となる.

同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

Max = 100
a = (1..Max).inject {|r, i| r + i ** 2}
b = (1..Max).inject(:+) ** 2
puts b - a


（問７）
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.

def set_f(i)
  for j in 2..(Max.div(i))
    $a[i * j] = 2
  end
end

Max = 20_0000
$a = Array.new(Max)

for i in 2..Max
  if $a[i] != 2 
    $a[i] = 1
    set_f(i)
  end
end

counter = 0
for i in 2..Max
  if $a[i] == 1
    counter += 1
    break if counter == 1_0001
  end
end
puts i

エラトステネスの篩（参照）を使って求めました。問題はいくつくらいまでの素数を求めるかです。ここでは余裕を見て、200000以下の素数をすべて求めています。標準添付ライブラリの Prime を使えば、もっと簡単に書けます。

require 'prime'

i = 0
Prime.each.each do |prime|
  i += 1
  next if i != 1_0001
  puts prime
  break
end