Div Game

题目描述

给定一个正整数 $N$。考虑对 $N$ 反复施行以下操作：

首先，选择一个正整数 $z$，满足以下所有条件： $z$ 可以表示为 $z=p^e$，其中 $p$ 是一个素数，$e$ 是一个正整数； $z$ 整除 $N$； $z$ 与之前操作中选择的所有整数都不同。

然后，用 $N/z$ 替换 $N$。

求该操作最多可以施行多少次。

输入格式

输入按照下列格式从标准输入给出： $N$

输出格式

输出该操作最多可以施行的次数。

24

3

1

0

64

3

1000000007

1

997764507000

7

提示

输入中的所有数值均为整数。 $1 \leq N \leq 10^{12}$例如我们可以通过下列选择将操作施行三次：

选择 $z=2 (=2^1)$。（现在我们有 $N=12$.） 选择 $z=3 (=3^1)$。（现在我们有 $N=4$.） 选择 $z=4 (=2^2)$。（现在我们有 $N=1$。）
我们无法进行任何操作。
例如我们可以通过下列选择将操作施行三次：

选择 $z=2 (=2^1)$。（现在我们有 $N=32$.） 选择 $z=4 (=2^2)$。（现在我们有 $N=8$.） 选择 $z=8 (=2^3)$。（现在我们有 $N=1$。）
例如我们可以通过下列选择将操作施行一次：

$z=1000000007 (=1000000007^1)$。（现在我们有 $N=1$。）

标签: AtCoder|abc169D

来源

AtCoder|abc169D