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