杭電OJ(HDOJ):七夕祭り

タイトル:
1つの数nを入力して、この数のすべての因子とを探し出して、数字Nの因子はすべてNより小さくてまたNによって除去することができるすべての正の整数で、例えば12の因子は1,2,3,4,6があります.和は1+2+3+4+6=16です.入力データの1行目は、テストデータのグループ数を示す数字T(1<=T<=500000)である.次にT組のテストデータであり、各組のテストデータは1つの数字N(1<=N<=500000)しかなく、Nのすべての因子和を出力する.
入力例:
3 2 10 20
出力例:
1 8 22
ソリューション:
直接窮挙するとタイムアウトし,時間複雑度の最適化が必要となる:12のすべての因子が1,2,3,4,6,2がその因子であり,6もその因子である.6以降の数は使わなくてもいいので、時間を大幅に節約できます.

#include<stdio.h>

int main()
{
    int sum,t,n,i,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=1;
        m=n;
        for(i=2; i<m; ++i)
            if(n%i==0)
            {
                sum+=i;
                if(i*i!=n)// if i*i=n then sum only add i once
                    sum+=n/i;
                m=n/i;
            }
        printf("%d
",sum);
    }
}