题目描述
一个整数,除了本身以外的其他所有约数的和如果等于该数,那么我们就称这个整数为完全数。
例如,6就是一个完全数,因为它的除了本身以外的其他约数的和为 1+2+3 = 6。
现在,给定你N个整数,请你依次判断这些数是否是完全数。
输入格式
第一行包含整数N,表示共有N个测试用例。
接下来N行,每行包含一个需要你进行判断的整数X。
输出格式
每个测试用例输出一个结果,每个结果占一行。
如果测试数据是完全数,则输出“X is perfect”,其中X是测试数据。
如果测试数据不是完全数,则输出“X is not perfect”,其中X是测试数据。
数据范围
1≤N≤100,
1≤X≤108
输入样例:
3
6
5
28
输出样例:
6 is perfect
5 is not perfect
28 is perfect
思路
1.暴力, 超时
2.试除法解决问题
c++ 暴力 超时
#include <iostream>
using namespace std;
int main(){
int n, a;
int sum = 0;
cin >> n;
while(n --){
cin >> a;
sum = 0;
for(int i = 1; i <= a; i ++){
for(int j = i; j <= a; j ++){
int tmp = i * j;
if(tmp == a) sum += i + j;
}
}
if(sum - a == a){
printf("%d is perfect\n", a);
}else{
printf("%d is not perfect\n", a);
}
}
return 0;
}
C++ 试除法
#include <iostream>
using namespace std;
int main(){
int n, a;
int sum = 0;
cin >> n;
while(n --){
cin >> a;
//特判1,自身的情况
if(a == 1) sum = 0;
else sum = 1;
for(int i = 2; i <= a / i; i ++){
if(a % i == 0) sum += i + a / i;
}
if(sum == a){
printf("%d is perfect\n", a);
}else{
printf("%d is not perfect\n", a);
}
}
return 0;
}
#include <iostream>
using namespace std;
int main(){
int n, a;
int sum = 0;
cin >> n;
while(n --){
cin >> a;
sum = 0;
for(int i = 1; i <= a / i; i ++){
if(a % i == 0) sum += i + a / i;
}
if(sum - a == a){
printf("%d is perfect\n", a);
}else{
printf("%d is not perfect\n", a);
}
}
return 0;
}
y总代码
#include <iostream>
using namespace std;
int main(){
int n, x;
int sum;
cin >> n;
while(n --){
cin >> x;
sum = 0;
for(int i = 1; i * i <= x; i ++){
if(x % i == 0){
if(i < x) sum += i; //保证1不算完全数
//当i == i的情况,上面s += i做过了
//x / i < x 保证不加自身,比如数28, i = 1, x / i = 28
if(i != x / i && x / i < x) sum += x/ i;
}
}
if(sum == x){
printf("%d is perfect\n", x);
}else{
printf("%d is not perfect\n", x);
}
}
return 0;
}