华为机试题——HJ56 完全数计算

描述

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。

它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

输入n，请输出n以内(含n)完全数的个数。

数据范围： 1 \le n \le 5 \times 10^{5} \1≤n≤5×105

输入描述：

输入一个数字n

输出描述：

输出不超过n的完全数的个数

示例1

输入：

1000

复制输出：

3

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
int checkCompletely(int num)                //检查输入的数字是否是完全数
{
    std::vector<int> numVect;
    for(int i = 1; i <= num; ++i)
    {
        if(num % i == 0)                  //说明可以整除
        {
            numVect.push_back(i);
            numVect.push_back(num / i);
        }
    }

    std::vector<int> tempVect;
    for(int i = 0; i < numVect.size() / 2; ++i)
    {
        tempVect.push_back(numVect.at(i));
    }

    int sum = 0;
    for(int ele : tempVect)
    {
        sum += ele;
    }
    
    if(sum == num * 2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int CompletelyNumber(int number)
{
    int count = 0;
    //1.先求每个数字的所有约数
    for(int i = 1; i <= number; ++i)
    {
        int flag = checkCompletely(i);
        if(flag)
        {
            count++;
        }
    }

    return count;
}

int main()
{
    int n;
    while(std::cin >> n)
    {
        int rtn = CompletelyNumber(n);
        std::cout << rtn << std::endl;
    }

    return 0;
}