求因子 c语言,C语言-求因子和

求因子和

题目描述:

一个数的因子和不包括它本身的所有因子之和，如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;

}