AT_abc169_d [ABC169D] Div Game

题目描述

给定一个正整数 $N$。对于 $N$，我们可以反复进行以下操作：

• 首先，选择一个满足以下所有条件的正整数 $z$：
  • 存在某个素数 $p$ 和正整数 $e$，使得 $z=p^e$；
  • $N$ 能被 $z$ 整除；
  • $z$ 与之前操作中选择的所有整数都不同；
• 将 $N$ 替换为 $N/z$。

请你求出最多可以进行多少次这样的操作。

输入格式

输入为标准输入，格式如下：

$N$

输出格式

请输出答案，结果为一个整数。

输入输出样例 #1

输入 #1

24

输出 #1

3

输入输出样例 #2

输入 #2

1

输出 #2

0

输入输出样例 #3

输入 #3

64

输出 #3

3

输入输出样例 #4

输入 #4

1000000007

输出 #4

1

输入输出样例 #5

输入 #5

997764507000

输出 #5

7

说明/提示

限制条件

• 输入为整数。
• $1 \leq N \leq 10^{12}$

样例解释 1

例如，可以按如下方式进行操作，共可进行 $3$ 次操作。

• 选择 $z=2\ (=2^1)$。（操作后，$N=12$）
• 选择 $z=3\ (=3^1)$。（操作后，$N=4$）
• 选择 $z=4\ (=2^2)$。（操作后，$N=1$）

样例解释 2

无法进行任何操作。

样例解释 3

例如，可以按如下方式进行操作，共可进行 $3$ 次操作。

• 选择 $z=2\ (=2^1)$。（操作后，$N=32$）
• 选择 $z=4\ (=2^2)$。（操作后，$N=8$）
• 选择 $z=8\ (=2^3)$。（操作后，$N=1$）

样例解释 4

例如，可以按如下方式进行操作，共可进行 $1$ 次操作。

• 选择 $z=1000000007\ (=1000000007^1)$。（操作后，$N=1$）

由 ChatGPT 4.1 翻译