UVA 10791

今天接着水一篇唯一分解定理的水题,题目如下:

   输入一个整数n(1<=n<2^32),求至少两个正整数,使得他们的最小公倍数为n,且这些整数的和最小,输出最小的和。

根据唯一分解定理n=a1^pq*a2^p2......不难得出结论,当ai^pi作为一个单独的整数时输出的和最小。

注意此题有两个坑:1、n==1时,输出最小值2,因为1+1=2;

2、当n为素数时,只有一种因子,而题目中要求最少两种,所以要补1;

3、注意n的范围,当n去极限值时,再进行补1操作时会造成最小数超出int类型的范围(因为这个莫名WA了好多次)。

4、当n为大于sqrt(n+0.5)的素数是应当直接加上;

下面直接给出AC代码,易错点在代码中进行标记。UVA 10791