prime_calculator.ex

defmodule PrimeCalculator do
  @moduledoc """
  Returns all prime numbers within a range
  """

  import Enum, only: [sort: 1, to_list: 1, filter: 2]
  import Map, only: [keys: 1, put: 3]
  import Float, only: [ceil: 1]
  import :math, only: [sqrt: 1]

  def call(n: max) do
    2..max
    |> to_list
    |> to_bool_map(%{})
    |> mark_non_primes(until: max)
    |> extract_primes
    |> sort
  end

  defp to_bool_map([n|numbers], state) do
    state = state |> update(n, prime?: true)

    to_bool_map numbers, state
  end

  defp to_bool_map([], state), do: state

  defp update(state, n, prime?: is_prime) do
    state |> put(n, is_prime)
  end

  defp mark_non_primes(state, until: max) do
    limit = sqrt(max) |> ceil |> round

    2..limit |> to_list |> mark_multiples(state, max)
  end

  defp mark_multiples([factor|numbers], state, max) do
    state = mark_non_prime(factor * 2, factor, state, max)

    numbers |> mark_multiples(state, max)
  end

  defp mark_multiples([], state, _), do: state

  defp mark_non_prime(n, factor, state, max) when n <= max do
    state = state |> update(n, prime?: false)

    n + factor |> mark_non_prime(factor, state, max)
  end

  defp mark_non_prime(_, _, state, _), do: state

  defp extract_primes(state) do
    state |> keys |> filter(&(prime?(state, &1)))
  end

  defp prime?(state, n), do: state[n]
end

defmodule PrimeCalculatorTest do
  use ExUnit.Case

  test "finds all primes from 1 to 2" do
    assert PrimeCalculator.call(n: 2) == [2]
  end

  test "finds all primes from 1 to 3" do
    assert PrimeCalculator.call(n: 3) == [2, 3]
  end

  test "finds all primes from 1 to 4" do
    assert PrimeCalculator.call(n: 4) == [2, 3]
  end

  test "finds all primes from 1 to 5" do
    assert PrimeCalculator.call(n: 5) == [2, 3, 5]
  end

  test "finds all primes from 1 to 7" do
    assert PrimeCalculator.call(n: 7) == [2, 3, 5, 7]
  end

  test "finds all primes from 1 to 20" do
    assert PrimeCalculator.call(n: 20) == [2, 3, 5, 7, 11, 13, 17, 19]
  end

  test "finds all primes from 1 to 100" do
    assert PrimeCalculator.call(n: 100) == [
      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
      43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
    ]
  end
end