Sieve - Exercism in Elixir

문제 보기

소수를 구하는 에라토스테네스의 체를 구현하는 문제였다. 개념은 쉬운데, 코드에서 나눗셈 또는 나머지 연산을 사용하지 말아야 한다는 조건이 붙었다(대신 곱셈을 사용하라는 의도). 우선 처음에 나눗셈을 사용해서 짠 간단한 코드는 이쪽.

defmodule Sieve do
  @doc """
  Generates a list of primes up to a given limit.
  """
  @spec primes_to(non_neg_integer) :: [non_neg_integer]
  def primes_to(limit) do
    2..limit//1
    |> Enum.to_list()
    |> do_primes_to([])
    |> Enum.reverse()
  end

  defp do_primes_to([], primes), do: primes
  defp do_primes_to([h | t], primes) do
    t
    |> Enum.reject(fn n -> rem(n, h) == 0 end)
    |> do_primes_to([h | primes])
  end
end

제출했더니 테스트 케이스는 통과하는데 아니나 다를까 나눗셈(rem 함수)을 사용하고 있다고 해서, 나눗셈 대신 곱셈을 사용하는 형태로 바꿔쓴 쪽이 이쪽이다. 다른 사람들의 답을 보니 정말 온갖 방법으로 나눗셈을 회피했더라. 어떻게 구현해도 뭐 상관없겠거니 싶다.

defmodule Sieve do
  @doc """
  Generates a list of primes up to a given limit.
  """
  @spec primes_to(non_neg_integer) :: [non_neg_integer]
  def primes_to(limit) do
    2..limit//1
    |> Enum.to_list()
    |> do_primes_to(limit, [])
    |> Enum.reverse()
  end

  defp do_primes_to([], _limit, primes), do: primes
  defp do_primes_to([h | t], limit, primes) do
    multies = Stream.unfold(1, fn n -> 
        if n * h > limit do
          nil
        else
          {n * h, n + 1}
        end
    end)
    |> Enum.to_list()

    t
    |> Kernel.--(multies)
    |> do_primes_to(limit, [h | primes])
  end
end