分数: 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