D - Div Game /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。

  • はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
    • ある素数 p と正の整数 e を用いて、 z=p^e と表せる
    • Nz で割り切れる
    • 以前の操作で選んだどの整数とも異なる
  • 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