leetcode-507-Perfect Number

题目描述：

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

 

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

 

Note: The input number n will not exceed 100,000,000. (1e8)

要完成的函数：

bool checkPerfectNumber(int num)

说明：

1、这道题给定一个数字，判断是不是完全数。完全数的定义是：除了本身之外的所有正因子之和等于这个数本身。

2、因为限制给定数字在一亿以内，并且完全数在一亿以内的，已知的，就只有五个……

所以朋友们都知道要怎么做……

代码如下：

　　 bool checkPerfectNumber(int num) 
    {
        if(num==6||num==28||num==496||num==8128||num==33550336)
            return true;
        else
            return false;
    }

实测6ms，beats 81.37% of cpp submissions。

已知的完全数推导公式由欧拉给出：如果p是质数，且2^p-1也是质数，那么（2^p-1）X2^（p-1）便是一个完全数。

也可以根据这个条件来判断，但是就这道题来说，上述解法是最直接的。

3、正常解法：

正常解法肯定是暴力破解啦，找到除了本身的所有正因子，看一下相加之和会不会等于本身。

代码如下：

    bool checkPerfectNumber(int num) 
    {
        if(num==1)//num==1为边界条件
            return false;
        int sum=1;
        int up=sqrt(num);
        for(int i=2;i<=up;i++)
        {
            if(num%i==0)
            {
                sum+=i+(num/i==i?0:num/i);//这一步还要做判断，因为比如49/7=7
            }　　　　　　　　　　　　　　　　　//我们这时候只需要加一个因子7
        }
        if(sum==num)
            return true;
        else
            return false;
    }

上述代码实测10ms，beats 16.77% of cpp submissions。