101693: [AtCoder]ABC169 D - Div Game

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给定一个正整数 $N$。重复以下操作: 首先,任意选择一个满足以下所有条件的正整数 $z$: * $z$ 可以表示为 $z=p^e$,其中 $p$ 是素数,$e$ 是正整数; * $z$ 整除 $N$; * $z$ 与之前操作中选择的所有整数不同。 然后,将 $N$ 修改为 $N/z$ 。 求最多可以进行的操作次数。 Translated by @[immccn123](https://www.luogu.com.cn/user/385633).

加入题单

上一题 下一题 算法标签: