Project Euler의 Smallest multiple을 Elixir로 풀기

진정한 프로그래밍 초보자에게 Elixir을 가르쳐 얻은 배우기 - Line 1: Error: Invalid Blog('by Esehara' ) 을 읽고 몇 가지 문제를 자신도 시도해 보았으므로 그 성과를 남겨 둡니다.

Smallest multiple

위의 기사에서는 「 Project Euler 자신의 경우, 특히 "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개의 자연수 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는 신선했습니다. 앞으로는 이러한 생각도 슬러슬러 할 수 있게 되어 가고 싶습니다.

추가

함수 gcd 이나 solve 입니다만, 패턴 매치를 사용해 이하와 같이 쓰는 편이 좋을지도 모르겠네요 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 씨, 고마워요!




C 언어 입문 - 입력한 두 자연수의 최소 공배수 구하기 - Webkaru  ↩

참고: 재귀 버전 유클리드 호제법 ¦ ↩

참고: The Pragmatic Bookshelf | Programming Elixir ¦ ↩