6871: ABC169 —— D - Div Game
[Creator : ]
Description
Given is a positive integer $N$. Consider repeatedly applying the operation below on $N$:
-
First, choose a positive integer $z$ satisfying all of the conditions below:
- $z$ can be represented as $z=p^e$, where $p$ is a prime number and $e$ is a positive integer;
- $z$ divides $N$;
- $z$ is different from all integers chosen in previous operations.
- Then, replace $N$ with $N/z$.
Input
Input is given from Standard Input in the following format:
$N$
$N$
Output
Print the maximum number of times the operation can be applied.
Constraints
All values in input are integers.
$1 \leq N \leq 10^{12}$
$1 \leq N \leq 10^{12}$
Sample 1 Input
24
Sample 1 Output
3
We can apply the operation three times by, for example, making the following choices:
- Choose $z=2 (=2^1)$. (Now we have $N=12$.)
- Choose $z=3 (=3^1)$. (Now we have $N=4$.)
- Choose $z=4 (=2^2)$. (Now we have $N=1$.)
Sample 2 Input
1
Sample 2 Output
0
We cannot apply the operation at all.
Sample 3 Input
64
Sample 3 Output
3
We can apply the operation three times by, for example, making the following choices:
- Choose $z=2 (=2^1)$. (Now we have $N=32$.)
- Choose $z=4 (=2^2)$. (Now we have $N=8$.)
- Choose $z=8 (=2^3)$. (Now we have $N=1$.)