[编程题]iNOC产品部--完全数计算

阳光穿透心脏的1/2处 2022-09-30 10:58 131阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。给定函数count(int n),用于计算n以内(含n)完全数的个数。计算范围, 0 < n <= 500000返回n以内完全数的个数。异常情况返回-1

**输入描述：**

输入一个数字

**输出描述：**

输出完全数的个数

**输入例子：**

1000

**输出例子：**

### 二、解题思路 ###

我想的是能把所有数是否为完全数的信息保存下来，这样在多次输入数字进行判断时就不用每次从 1 一直判断到当前数，这样对于多次输入的环境是十分有利的，但是代码就会显得麻烦一些，而且也会浪费存储空间。

代码：

#include <iostream>
    #include <bitset>
    #include <cmath>
    using namespace std;
    
    bool is_completenum(int i)
    {
        int sum = 0;
        for(int j = 1; j <= floor(pow(i, 0.5)); j++)
        {
            if(j != i && i%j == 0)
            {
                sum += j;
                int temp = i/j;
                if(temp != i && temp != j)
                {
                    sum += temp;
                }
            }
        }
        if(sum == i)
            return true;
        return false;
    }
    
    void test1()
    {
        bitset<500000> bs;
        bs.reset();
        for(int i = 1; i <= 10000; i++)
        {
            if(is_completenum(i))
                bs.set(i-1);
        }
        int n;
        while(cin >> n)
        {
            int count = 0;
            if(n > 10000)
            {
                for(int i = 10001; i <= n; i++)
                {
                    if(is_completenum(i))
                        bs.set(i-1);
                }
            }
            for(int i = 0; i < n; i++)
            {
                if(bs.test(i))
                    count++;
            }
            if(count)
                cout << count << endl;
            else
                cout << -1 << endl;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }

另外有解法是直接不保存，每次都从 1 开始计算。还有人更投机取巧，发现500000以下的完全数就只有 4 个，所以就有了以下的解法：

#include <iostream>
    #include <vector>
    #include<algorithm>
    using namespace std;
    vector<int> helper{ 6,28,496,8128 };
    int main() 
    {    
        int num;    
        while (cin >> num) 
        {        
            cout << upper_bound(helper.begin(), helper.end(), num) - helper.begin() << endl;    
        }    
        return 0;
    }