AtCoder Beginner Contest 169
翻译中…
Problem Statement
翻译中…
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$.
翻译中…
Find the maximum number of times the operation can be applied.
翻译中…
Constraints
翻译中…
- All values in input are integers.
$1 \leq N \leq 10^{12}$
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N翻译中…
Output
翻译中…
Print the maximum number of times the operation can be applied.
翻译中…
样例
Input #1
24
Output #1
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$.)
Input #2
1
Output #2
0
We cannot apply the operation at all.
Input #3
64
Output #3
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$.)
Input #4
1000000007
Output #4
1
We can apply the operation once by, for example, making the following choice:
- $z=1000000007 (=1000000007^1)$. (Now we have $N=1$.)
Input #5
997764507000
Output #5
7
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。