西安电子科技大学上机题（二）

题目： 写一个程序，给出指定整数范围[a ,b]内所有的完数，一个数如果恰好等于除它本身外的所有因子之和，这个数就称为完数，例如6是完数，因为6=1+2+3。

输入格式：

1
共一组数据，为两个正整数，分别表示a和b（1<a<b<10^5）

输出格式：

1
指定范围内的所有完数，每个数占一行

输入样例：

1
2
6
100

输出样例：

1
2
3
4
28
原题样例应该有误：是闭区间[6, 100]应当输出：
6
28

思路：

  • 循环遍历范围内所有的数
  • 求出每个数的因子有哪些
  • 求出因子的和看是否会等于当前数
  • 等于则保存在数组或者 vector 中

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h> 
using namespace std;

vector<int> getYinZi(int num) { // 求数的因子
    vector<int> yinzi;
    for(int i = num/2; i>=2; i--) {
        if(num % i == 0)
            yinzi.push_back(i);
    }
    return yinzi;
}

bool isWanShu(int num) { // 判断是否为完数
    vector<int> yinzi = getYinZi(num);
    vector<int>::iterator t;
    int sum = 0;
    for(t = yinzi.begin(); t != yinzi.end(); t++) {
        sum += *t;
    }
    sum += 1;
    if(sum == num)
        return true;
    else
        return false;
}

int main(void) {
    int begin = 0, end = 0;
    cin >> begin;
    cin >> end;
    for(int i = begin; i<=end; i++){ // 循环获取区间内的完数
        if(isWanShu(i))
            cout << i << endl;
    }
    return 0;
}

优化：

  • 可以使用 map 数据类型记录前面已经遍历过的数的因子，减少计算因子需要的时间，但同时会带来巨大的内存资源消耗，不建议使用。
  • 因子一定是属于素数和1组成，因此可以先计算出一定量的素数数组或者 vector ，再通过循环对素数列表进行求余，得到当前数的因子列表，再判断是否为完数。

注意点：
本题一定要先求因子，再求和计算，如果先求求和的数再判断是否为因子将计算量翻很多倍，算法效率极低。