AOJ Volume21 2101: Perfect Number

以前の約数を求める考え方では時間が足りない。
よって、半分で済むように i*i=nまでfor文をまわす。

この時、    i*i=nの時は sum+=i
そうでなければ  sum+= i + (n/i)として改善した。


問題文に「その数自身を除く約数の和を S とする．」とあることを忘れずに。


 /********************************
*  2012/07/04                           *
*  AOJ Volume21 2101             *
*  Perfect Number                   *
*  crane                                    *
*********************************/


#include<iostream>
#include<cmath>
using namespace std;


int main(){
    int n;
    while(cin >> n,n){
        int sum=0;
        for(int i=1; i*i<=n; i++)
            if(n % i == 0){
                if(i*i == n) sum+=i;
                else         sum += i+(n/i);
            }
        sum -= n;
        if(sum==n)      cout << "perfect number" << endl;
        else if(sum<n) cout << "deficient number" << endl;
        else                  cout << "abundant number" << endl;
    }
    return 0;
}

約数を求める

約数を求める。約数の個数はvectorのサイズでOK

/************************************
*   2012/07/04                      *
*   約数を求める。      *
*   ->個数はvectorのサイズで        *
*   crane                           *
*************************************/
#include<iostream>
#include<vector>
using namespace std;

int main(){
    int num;
    while(cin >> num){
        vector<int> data;
        data.push_back(1);
        int i=2;
        for(int i=2; i<=num+1; i++){
            if(num % i == 0) data.push_back(i);
        }       
        for(int i=0; i<data.size(); i++){
            if(0<i) cout << " ";
            cout << data[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}