defmodule Main do
  require Integer

  def main do
    n = IO.gets("") |> String.trim() |> String.to_integer()

    div_game(n) |> IO.puts()
  end

  @doc """
  div_game

  ## Examples

      iex> DivGame.div_game(24)
      3
      iex> DivGame.div_game(64)
      3
      iex> DivGame.div_game(1)
      0
      iex> DivGame.div_game(1000000007)
      1
      iex> DivGame.div_game(997764507000)
      7

  """
  def div_game(n) do
    M.factorization(n)
    |> Enum.map(fn [_, p] -> p end)
    |> Enum.map(&divide/1)
    |> Enum.sum()
  end

  defp divide(n) do
    Stream.iterate(1, &(&1 + 1))
    |> Enum.reduce_while({n, 0}, fn i, {acc_n, acc_cnt} ->
      rem = acc_n - i
      if rem < 0, do: {:halt, {rem, acc_cnt}}, else: {:cont, {rem, acc_cnt + 1}}
    end)
    |> elem(1)
  end
end

# https://qiita.com/sym_num/items/c7ad291644a55d6c0419
defmodule M do
  def normal(n) do
    W.factor([], n, 2, trunc(:math.sqrt(n)))
    |> compress
  end

  def factorization(n) when n < 10000 do
    W.factor([], n, 2, trunc(:math.sqrt(n)))
    |> compress
  end

  def factorization(n) do
    limit = trunc(:math.sqrt(n))
    factors1(10, n, 2, div(limit, 10) + 1, limit)
    factors2(10, []) |> Enum.sort() |> sieve |> adjust(n) |> compress |> Enum.reverse()
  end

  def compress(ls) do
    Enum.chunk_by(ls, fn n -> n end)
    |> Enum.map(fn x -> [hd(x), length(x)] end)
    |> Enum.reverse()
  end

  def factors1(1, n, start, _, limit) do
    pid = spawn(W, :part, [])
    send(pid, {self(), {n, start, limit}})
  end

  def factors1(c, n, start, add, limit) do
    stop = start + add
    pid = spawn(W, :part, [])
    send(pid, {self(), {n, start, stop}})
    factors1(c - 1, n, stop + 1, add, limit)
  end

  def factors2(0, ls) do
    ls
  end

  def factors2(n, ls) do
    receive do
      {:answer, msg} ->
        factors2(n - 1, msg ++ ls)
    end
  end

  def sieve([]) do
    []
  end

  def sieve([l | ls]) do
    [l] ++ sieve(sieve1(ls, l, []))
  end

  def sieve1([], _, res) do
    Enum.reverse(res)
  end

  def sieve1([l | ls], x, res) do
    if rem(l, x) == 0 && x != l do
      sieve1(ls, x, res)
    else
      sieve1(ls, x, [l] ++ res)
    end
  end

  def adjust(l, x) do
    if Enum.member?(l, x) do
      [x]
    else
      l
    end
  end
end

defmodule W do
  def part do
    receive do
      {sender, {n, start, stop}} -> send(sender, {:answer, W.factor([], n, start, stop)})
    end
  end

  def factor(p, n, x, limit) do
    cond do
      n == 1 -> p
      x > limit -> [n | p]
      rem(n, x) == 0 -> factor([x | p], div(n, x), x, limit)
      x == 2 -> factor(p, n, 3, limit)
      rem(x, 2) == 0 -> factor(p, n, x + 1, limit)
      true -> factor(p, n, x + 2, limit)
    end
  end
end