题目描述

一个整数，除了本身以外的其他所有约数的和如果等于该数，那么我们就称这个整数为完全数。

例如，6就是一个完全数，因为它的除了本身以外的其他约数的和为 1+2+3 = 6。

现在，给定你N个整数，请你依次判断这些数是否是完全数。

输入格式
第一行包含整数N，表示共有N个测试用例。

接下来N行，每行包含一个需要你进行判断的整数X。

输出格式
每个测试用例输出一个结果，每个结果占一行。

如果测试数据是完全数，则输出“X is perfect”，其中X是测试数据。

如果测试数据不是完全数，则输出“X is not perfect”，其中X是测试数据。

数据范围

1≤N≤100,
1≤X≤10^8

输入样例：

3
6
5
28

输出样例：

6 is perfect
5 is not perfect
28 is perfect

时间复杂度

C++一秒只能处理1亿数，即10^8；本题目1≤N≤100,1≤X≤10^8；最大极限会导致超时，所以不能用X=10^8做最大循环，需要简化。
如果i是X的约数，那么x/i也一定是其约数，i从1开始，所以i<x/i,即i*i<x,i<x^(1/2)，此时最大循环数是10^8 * 10^(1/2) * 100 = 10^6;满足时间复杂度

C++ 代码

#include<iostream>
using namespace std;

int main() {

        int X,N,sum=0;
        cin>>N;
   for(int j=0;j<N;j++){

        cin>>X;
        for(int i=1;i*i<X;i++) {
            if(X%i==0) {
                if(i<X) {
                    sum+=i;
                }
                if(X/i<X&&X/i!=i) {
                    sum+=X/i;
                }
            }

        }
        if(sum==X) {
            cout<<X<<" is perfect"<<endl;
        }else {
            cout<<X<<" is not perfect"<<endl;
        }
        sum=0;

    }
}