LoginSignup
7

More than 5 years have passed since last update.

Project EulerのSmallest multipleをElixirで解く

Last updated at Posted at 2016-11-07

本当のプログラミング初心者にElixirを教えたことで得た学び - Line 1: Error: Invalid Blog('by Esehara' )を読んで、いくつかの問題を自分も試しにやってみたのでその成果を残しておきます。

Smallest multiple

上の記事では「Project Euler」というサイトにある問題をElixirで解いていくことについて触れられています。自分の場合、特に「Smallest multiple」という問題が印象に残りました。

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

1から10までの自然数の最小公倍数は2520になるそうですが、1から20だとどうか?という問題です。

考え方

まずは問題を解くための考え方ですが、自分は以下のYahoo!知恵袋の解答が参考になりました。

1~10までの自然数の最小公倍数が2520となるようですが、どのようにし... - Yahoo!知恵袋

ベストアンサーの解答はすでに2520という数字が分かっていたとき、なぜ1から10までの自然数の最小公倍数になるかを説明しているように見えますが、他の解答は違うアプローチを取っていました。特に、実際に問題を解くときは解答の後半にある

1と2の最小公倍数は2、
2と3の最小公倍数は6、
6と4の最小公倍数は12、
12と5の最小公倍数は60、
60と6の最小公倍数は60、
60と7の最小公倍数は420、
420と8の最小公倍数は840、
840と9の最小公倍数は2520

この考え方を使って、再帰でプログラムを書くことにしました。

最小公倍数と最大公約数

プログラムを書くにあたって、まず2つの自然数の最小公倍数を求める必要があります。

2つの自然数a, bの最大公約数をGCDとすると最小公倍数LCMは次の公式で求められます。1

LCM = \frac{a \times b}{GCD}

このため、まずは最小公倍数を求める必要があります。最小公倍数はユークリッド互除法で求めることができます。だいたい以下のように書けるかと思います。2

defmodule Problem5 do
  def gcd(a, b) do
    if rem(a, b) == 0 do
      b
    else
      gcd(b, rem(a, b))
    end
  end
end

Elixirに演算子%はないため、remを使います。

上のプログラムを用いて、例えば824と128の最大公約数を求めたい場合は以下のようにします。

IO.puts Problem5.gcd(824, 128) # 8

次に、先ほどの考え方を用いて最小公倍数を求めていきます。自分はこのように書きました。

defmodule Problem5 do
  def gcd(a, b) do
    if rem(a, b) == 0 do
      b
    else
      gcd(b, rem(a, b))
    end
  end

  def solve(n, lcm, max) do
    if n == max do
      lcm
    else
      lcm_next = div(n * lcm, gcd(n, lcm))
      solve(n+1, lcm_next, max)
    end
  end
end

引数nに与えた自然数がmaxに到達するまでループします。Elixirでは、除算で整数値を返したい場合はdivを使います。

iex(1)> 6 / 2
3.0
iex(2)> div(6, 2)
3

これを用いて、問題の答えを求めると、

IO.puts Problem5.solve(2, 1, 10) # 2520
IO.puts Problem5.solve(2, 1, 20) # 232792560

といったようになります。

感想

自分は普段再帰を使うことがほとんどなかったため、whileなどを使えず、再帰で書くことを求められるElixirは新鮮でした。今後はこのような考え方もスラスラできるようになっていきたいと思います。

追記

関数gcdsolveですが、パターンマッチを使って以下のように書いたほうがいいかもしれませんね3。 最初に書いたときよりもかなりすっきりしました。

defmodule Problem5 do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x, y))

  def solve(max, lcm, max), do: lcm
  def solve(n, lcm, max) do
    lcm_next = div(n * lcm, gcd(n, lcm))
    solve(n+1, lcm_next, max)
  end
end

さらに追記

コメントにてご指摘を頂いたのですが、今のままだとProblem5.solve(2, 1, 11)の計算結果が違いますね・・・。コメントでは修正版も教えていただいていますが、一応記事本文にも修正版を書いておきます。

defmodule Problem5 do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x, y))

  def solve(max), do: solve(2, 1, max)
  def solve(max, lcm, max), do: div(max * lcm, gcd(max, lcm))
  def solve(n, lcm, max) do
    lcm_next = div(n * lcm, gcd(n, lcm))
    solve(n+1, lcm_next, max)
  end
end

地味にsolve/1も追加してあります。こうしておくことで、

IO.puts Problem5.solve(10) # 2520
IO.puts Problem5.solve(11) # 27720
IO.puts Problem5.solve(20) # 232792560

などと書けるようになります。これもコメントにて教えて頂いたものです。mhgpさん、ありがとうございました! :smile:


Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7