拜托了,牛老师
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

时钟指向0点,又是新的一天。今天是七夕节,看着朋友圈牛、牛、牛陈、牛余、牛lan等脱单牛准点发送的虐牛图,牛牛心理丝毫没有波动,因为他在协助科研人员制作新牛病毒的疫苗!
手机突然传来消息提醒:
七夕节有空出来一起吃饭吗?好久没见你了,想见你!——牛妹(清楚姐姐扮演)
疫苗的研发已经剩下最后一个难关:
定义一个函数 f(n) 为将 n 进行严格的因数分解(因数不重复,且分解的因数个数要大于1)后,使得所分解的因数之和最小的值,现在给出一个正整数 n,能否算出 f(n) ?
牛牛太想和牛妹一起过七夕节了,但他对这个问题毫无头绪,你能帮帮他解决这个问题吗?拜托了,牛老师!

输入描述:

输入一个整数n,2 <= n <= 106

输出描述:

输出一个整数,表示 f(n) 的值。
示例1

输入

复制
18

输出

复制
9

说明

18可以分解成 1 * 18,2 * 9,3 * 6,显然 3 + 6 = 9是最优的(18 = 2 * 3 * 3 由于有重复值所以无法得到)。
示例2

输入

复制
3

输出

复制
4

说明

3可以分解成1 * 3(因数个数必须大于1),所以答案为4。

备注:

向奋战在科研(刷题)一线无暇过七夕节的英雄们致敬!