荷兰信息学奥林匹克 2025-2026 第一轮

A3. NIO 数（NIO-getal）

赛事： Nederlandse Informatica Olympiade 赛季： 2025-2026 阶段： 第一轮（Eerste ronde）

---

题目描述

在本题中，对于一个正整数 (n)（(n>1)），定义它的 NIO 数 (N(n))。

计算方法如下。

情况 1：(n) 不是质数

如果整数 (n) 本身不是质数，那么将 (n) 写成 2 个或更多质数的乘积：

$$n=p_1\times p_2\times \cdots \times p_k$$

算术基本定理说明：

每一个不是质数的正整数，都能够唯一地分解为若干个质数的乘积。

质数是指：

大于 1，并且只有两个不同正整数因数——1 和它本身——的正整数。

因此：

$$1$$

不是质数。

例如：

$$60=2\times2\times3\times5$$

为了求出它的 NIO 数，需要把质因数分解中的每一个质数 (p) 替换为：

$$p+1$$

然后将这些新的数全部相乘。

因此：

$$N(60) =(2+1)\times(2+1)\times(3+1)\times(5+1)$$ $$=3\times3\times4\times6 =216$$

---

情况 2：(n) 本身是质数

如果 (n) 本身就是一个质数 (p)，那么定义：

$$N(n)=p+1$$

例如：

$$7$$

是一个质数，因此：

$$N(7)=7+1=8$$

---

输入格式

编写一个程序，从标准输入读取一行。

这一行包含一个整数：

n

满足：

$$2\le n\le10000$$

---

输出格式

向标准输出输出一行，其中包含：

$$N(n)$$

也就是整数 (n) 对应的 NIO 数。

程序时间限制为：

1 秒

---

样例 1

输入：

60

输出：

216

---

样例 2

输入：

1001

输出：

1344

---

样例 3

输入：

1024

输出：

59049

测试点编号	输入 n	难度层级	特殊性质	标准输出	设计目的
1		弱数据	最小值、无质因数	1	检查循环不执行时的初始结果
2	16		单一质因数、2⁴	81	检查同一质因数被重复处理
3	210	正常数据	四个不同质因数	576	检查多个质因数的连续分解
4	99991		较大质数	99992	检查循环后剩余大质因数的处理
5	1000000	极限数据	2⁶×5⁶、重复质因数	34012224	检查较大输入及多次乘法运算