紫书10-4 最小公倍数的最小和（Minimum Sum LCM ） UVA10791

题意：给一个整数n，求至少两个各不同的正整数，让它们的最小公倍数为n，且这些整数的和最小. 回顾下紫书的一些知识点。 我们知道，lcm（a，b）=a*b/gcd(a,b).但这还不够。 事实上，gcd是对a与b做唯一分解后，对每个质因子取最小值相乘，而lcm就是对每个质因子取最大相乘。 整了这么多，如何让这个数的和最小呢？先考虑极限极限情况，假设就是n和1，这个时候就是n+1.那么怎么让它变小呢？没错！就是唯一分解，只要把lcm(a,b)中的一个数拿出来单独作为一个新的整数，会比之前小很多。 假设不拿之前是n吧.拿了之后是n除以这个因子再加上这个因子！贪心地想每个唯一分解出来的素数作为新的正整数时，和就是最小的！那么问题就转化为求n的唯一分解式子里每个因子的求和。 注意，当n是一个素数或者仅有一个因子的时候，没有足够的因子满足题目的不同正整数，要“借”一个“1”，所以是n+1. 记得再构造一个素数表. 代码：

#include
using namespace std;
const int maxn = 1e7+2;
int prime[maxn];int cal[maxn];
int cnt=0;bool vis[maxn];
void pre(int n){
	memset(vis,0,sizeof(vis));
	for(int i=2;i