Rubyでピタゴラスを求める 〜Rubyでオイラープロジェクトを解こう！Problem9

Problem 9 - Project Eulerより

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

For example, .
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
ピタゴラス数とは、次の関係にある3つの自然数の組(a < b < c )をいう。

例： .
a + b + c = 1000 となるピタゴラス数がただ一つある。abcの積を求めよ。

a < b < c の条件を維持しながら
a + b + c = 1000 なるピタゴラス数を
順番に探していく

def sum_of_pythagoras(sum)
  a = 1; b, c = a+1, a+2
  limit = sum
  loop do
    if pythagoras?(a, b, c) and (a + b + c) == sum
      return a, b, c
    end
    c += 1
    if c > limit
      b += 1; c = b + 1
    end
    if b > limit/2
      a += 1; b = a + 1; c = b + 1
    end
    return nil if a > limit/3
  end
end

def pythagoras?(a, b, c)
  return true if (a ** 2 + b ** 2) == c ** 2
  false
end

t =  Time.now
a, b, c = sum_of_pythagoras(1000)
"#{a} * #{b} * #{c} = #{a*b*c}" # => "200 * 375 * 425 = 31875000"
Time.now - t # => 70.728619

ちょっと時間が掛かる
(a + b + c) == sum を先に評価するようにしたら…

def sum_of_pythagoras(sum)
  a = 1; b, c = a+1, a+2
  limit = sum
  loop do
    if (a + b + c) == sum and pythagoras?(a, b, c)
      return a, b, c
    end
    c += 1
    if c > limit
      b += 1; c = b + 1
    end
    if b > limit/2
      a += 1; b = a + 1; c = b + 1
    end
    return nil if a > limit/3
  end
end

def pythagoras?(a, b, c)
  return true if (a ** 2 + b ** 2) == c ** 2
  false
end

t =  Time.now
a, b, c = sum_of_pythagoras(1000)
"#{a} * #{b} * #{c} = #{a*b*c}" # => "200 * 375 * 425 = 31875000"
Time.now - t # => 34.074137

時間が半分になった