← 返回题目列表

AtCoder · abc169_d

D. Div 游戏

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给定的是一个正整数 N。考虑重复应用以下操作 N:

  • 首先,选择一个正整数 z 满足以下所有条件:
    • z 可以表示为 z=p^e,其中 p 是素数并且 e 是正整数;
    • z 划分 N;
    • z 与之前操作中选择的所有整数不同。
  • 然后,替换 N 与 N/z.

查找可以应用该操作的最大次数。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^{12}

输入

输入由标准输入按以下格式给出:

N

输出

打印可以应用该操作的最大次数。


示例输入 1

24

示例输出 1

3

我们可以通过做出以下选择来应用该操作三次:

  • 选择 z=2 (=2^1)。 (现在我们有 N=12.)
  • 选择 z=3 (=3^1)。 (现在我们有 N=4.)
  • 选择 z=4 (=2^2)。 (现在我们有 N=1.)

示例输入 2

1

示例输出 2

0

我们根本无法应用该操作。


示例输入 3

64

示例输出 3

3

我们可以通过做出以下选择来应用该操作三次:

  • 选择 z=2 (=2^1)。 (现在我们有 N=32.)
  • 选择 z=4 (=2^2)。 (现在我们有 N=8.)
  • 选择 z=8 (=2^3)。 (现在我们有 N=1.)

示例输入 4

1000000007

示例输出 4

1

我们可以通过例如做出以下选择来应用一次操作:

  • z=1000000007 (=1000000007^1)。 (现在我们有 N=1.)

示例输入 5

997764507000

示例输出 5

7