九度OJ 1050：完数 （数字特性）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：7535

解决：3125

题目描述：

求1-n内的完数，所谓的完数是这样的数，它的所有因子相加等于它自身，比如6有3个因子1,2,3,1+2+3=6，那么6是完数。即完数是等于其所有因子相加和的数。

输入：

测试数据有多组，输入n，n数据范围不大。

输出：

对于每组输入,请输出1-n内所有的完数。如有案例输出有多个数字，用空格隔开，输出最后不要有多余的空格。

样例输入：

6

样例输出：

6

来源：

2010年哈尔滨工业大学计算机研究生机试真题

思路：

求出所有的因子，然后相加即可。

此题实际上只需要循环到sqrt(n)，后面的因子用前面求出来的就能求，时间复杂度会大大下降。

代码：

#include <stdio.h>

int main(void)

{

    int n, i, j;

    int count;

    int sum;

    while (scanf("%d",&n) != EOF)

    {

        count = 0;

        for (j=1; j<=n; j++)

        {

            sum = 0;

            for (i=1; i<=j/2; i++)

            {

                if (j % i == 0)

                    sum += i;

            }

            //printf("sum=%d", sum);

            if (sum == j)

            {

                count ++;

                if (count > 1)

                    printf(" ");

                printf("%d", j);

            }

        }

        printf("\n");

    }

    return 0;

}

/**************************************************************

    Problem: 1050

    User: liangrx06

    Language: C

    Result: Accepted

    Time:120 ms

    Memory:912 kb

****************************************************************/