/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。
- はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
- ある素数 p と正の整数 e を用いて、 z=p^e と表せる
- N が z で割り切れる
- 以前の操作で選んだどの整数とも異なる
- N を、N/z に置き換える
最大で何回操作を行うことができるか求めてください。
制約
- 入力はすべて整数である。
- 1 \leq N \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
24
出力例 1
3
例えば、次のように操作を行うことで、 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
例えば、次のように操作を行うことで、 3 回操作を行うことができます。
- z=2 (=2^1) とする。( 操作後、 N=32 となる。)
- z=4 (=2^2) とする。( 操作後、 N=8 となる。 )
- z=8 (=2^3) とする。( 操作後、 N=1 となる。 )
入力例 4
1000000007
出力例 4
1
例えば、次のように操作を行うことで、 1 回操作を行うことができます。
- z=1000000007 (=1000000007^1) とする。( 操作後、 N=1 となる。 )
入力例 5
997764507000
出力例 5
7
Score : 400 points
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.
Sample Input 1
24
Sample 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.)
Sample Input 2
1
Sample Output 2
0
We cannot apply the operation at all.
Sample Input 3
64
Sample 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.)
Sample Input 4
1000000007
Sample 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.)
Sample Input 5
997764507000
Sample Output 5
7