1317 - 最小因子和

一个正整数n>1,有多种因子分解方式,比如24=1*24=2*12=3*8=4*6=2*2*6=2*2*2*3。把每一种分解中的因子相加,求出最小因子之和的那种分解方式。比如前面的例子中,24=1*24,则因子之和为1+24=25, 24=2*12,因子之和为2+12=14。可以看出因子之和最小的那种分解方式为24=2*2*2*3.

如果n是质数,则输出n+1。

输入

输入一个正整数n。

输出

输出和最小的那种分解形式的因子之和。

样例

输入

24

输出

9

输入

7

输出

7

提示

样例1解释:24=1*24,则因子之和为1+24=25, 24=2*12,因子之和为2+12=14。可以看出因子之和最小的那种分解方式为24=2*2*2*3. 将因子求和得到2+2+2+3=9.

对于100%的数据,1< n<=1e9。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题