エラトステネスの篩 for 素因数分解

sieve_of_eratosthenes.exs

defmodule SieveOfEratosthenes do

  def run(n) do
    sqrt = :math.sqrt(n) |> floor()

    {time, d} = :timer.tc(SieveOfEratosthenes, :init_d, [n])
    IO.inspect(time, label: "init d time")

    # 偶数を飛ばす
    Stream.iterate(13, &(&1 + 2))
    |> Stream.take_while(&(&1 <= sqrt))
    # 3, 5, 7, 11 の倍数は見ているので飛ばす
    |> Stream.reject(&(rem(&1, 3) == 0))
    |> Stream.reject(&(rem(&1, 5) == 0))
    |> Stream.reject(&(rem(&1, 7) == 0))
    |> Stream.reject(&(rem(&1, 11) == 0))
    |> Enum.to_list()
    |> process(n, d)
  end

  def process([], _, d), do: d
  def process([i | t], n, d) do
    d =
      case d[i] do
        ^i ->
          d = Map.put(d, i, i)

          dd =
            Stream.iterate(2 * i, &(&1 + i))
            |> Stream.take_while(&(&1 <= n))
            # すでに因数が格納されているものは飛ばす
            |> Stream.filter(fn j -> d[j] == j end)
            |> Stream.map(fn j -> {j, i} end)
            |> Enum.to_list()
            |> Map.new()

          Map.merge(d, dd)

        _ -> d
    end

    process(t, n, d)
  end

  def init_d(n) do
    for i <- 1..n do
      cond do
        rem(i, 2) == 0 -> {i, 2}
        rem(i, 3) == 0 -> {i, 3}
        rem(i, 5) == 0 -> {i, 5}
        rem(i, 7) == 0 -> {i, 7}
        rem(i, 11) == 0 -> {i, 11}
        true -> {i, i}
      end
    end
    |> Map.new()
  end

  def test() do
    n = 1000_000
    {time, r} = :timer.tc(SieveOfEratosthenes, :run, [n])
    IO.inspect(r)
    IO.inspect(time)
  end

end

SieveOfEratosthenes.test()

run time is 1462ms...
too slow 😢