求因子和
题目描述:
一个数的因子和不包括它本身的所有因子之和，如12的因子有1、2、3、4、6所以12的因子和是16。现在给定一个数n(n<=10^9)，求它的因子和。
输入格式:
一个数。
输出格式:
一个数。
样例输入:
12
样例输出:
16
提示:
60%的数据，n<=10,000;
80%的数据，n<=1,000,000;
100%的数据，n<=1,000,000,000;
这题第一次写的时候，一般人都会想到直接枚举，即直接从1一直枚举到该数除本身的最大因子。于是有了下面这一段代码：
#include
int main()
{
long n, s = 0, x;
int i;
scanf(“%ld”, &n);
for (i = 1; i < n; i++){
if (n % i == 0)
s += i;
}
printf(“%ld”, s);
return 0;
}
但是这段代码一遇到大数就超时。原因是从1一直枚举到最大因子数量太多，效率太低。这里有一种解决方案，就是当枚举一个因子时，立马将输入的数除以这个因子，这样就可以只枚举到n的算术平方根了。代码如下：
#include
#include
int main()
{
long n, s = 0;
int i;
scanf(“%ld”, &n);
for (i = 1; i <= sqrt(n); i++){
if (n % i == 0)
if (i == n / i)
s += i;
else
s = s + i + n / i;
}
printf(“%ld”, s – n);
return 0;
}