#1821. [GESP202412 五级] 奇妙数字

[GESP202412 五级] 奇妙数字

题目描述

小杨认为一个数字 xx 是奇妙数字当且仅当 x=pax=p^a,其中 pp 为任意质数且 aa 为正整数。例如,8=238=2^3,所以 88 是奇妙的,而 66 不是。

对于一个正整数 nn,小杨想要构建一个包含 mm 个奇妙数字的集合 {x1,x2,⋯ ,xm}\{x_1,x_2,\cdots,x_m\},使其满足以下条件:

  • 集合中不包含相同的数字。
  • x1×x2×⋯×xmx_1\times x_2\times \cdots\times x_m 是 nn 的因子(即 x1,x2,⋯ ,xmx_1,x_2,\cdots,x_m 这 mm 个数字的乘积是 nn 的因子)。

小杨希望集合包含的奇妙数字尽可能多,请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

输入格式

第一行包含一个正整数 nn,含义如题面所示。

输出格式

输出一个正整数,代表满足条件的集合最多包含的奇妙数字个数。

样例

128
3

题目来源:洛谷 B4070