题解 | 完数VS盈数

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

int is_wanshu(int n){
    vector<int> factors;
    for(int i=1;i<=n/2;i++){
        if(n%i==0){
            factors.push_back(i);
        }
    }
    int sum=0;
    for(int f:factors){
        sum+=f;
    }
    if(sum==n){
        return 1;
    }else if(sum>n){
        return 0;
    }
    return -1;
}

vector<int> E,G;

int main() {
    for(int i=2;i<=60;i++){
        int type=is_wanshu(i);
        if(type==1){
            E.push_back(i);
        }else if(type==0){
            G.push_back(i);
        }
    }

    cout<<"E: ";
    for(int e:E){
        cout<<e<<" ";
    }
    cout<<endl;
    cout<<"G: ";
    for(int g:G){
        cout<<g<<" ";
    }
}
// 64 位输出请用 printf("%lld")

关键点：

1. 求某个数n的因子时只遍历n/2即可：因为某个数n的最大因子一定小于n/2;
2. for(int i=1;i<=n/2;i++){
3. if(n%i==0){
4. factors.push_back(i);
5. }
6. }