[LeetCode][Python]507.Perfect Nu

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)

思路：

1. 首先，当然要知道如何得到一个数的divisiors，或者得到一个数是完全数。最简单粗暴的方法，从1到这个数依次看能否被这个数整除。
   def checkPerfectNumber(self, num):
   """
   :type num: int
   :rtype: bool
   """
   sum = 0
   for i in xrange(1, num):
   if (num%i==0):
   sum += i
   if(sum==num):
   return True
   else:
   return False
   但是不幸，在num很大的情况下超时了。
   继续分析：28 = 1 + 2 + 4 + 7 + 14
   对于2，满足条件，则28/2=14也满足条件，4满足条件，则28/4也满足条件。
   所以可以对数字从2到sqrt(num)进行查看，如果满足取模运算为0，则把这个数和num除以这个数的值放到sum里面去。判断是否和num相等即可。

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        sum = 0
        for i in xrange(1, num):
            if (num%i==0):
                sum += i
        if(sum==num):
            return True
        else:
            return False

    def checkPerfectNumber2(self, num):
        total, i = 1, 2
        while i*i < num:
            if num%i==0:
                total += i + num/i
            i+=1
        return num>1 and total==num

    def checkPerfectNumber3(self, num):
        if num<=1:
            return False
        sum = cur = 1
        while cur<int(num**0.5):
            cur+=1
            if(num%cur == 0):
                sum += cur + num/cur
        return sum == num

if __name__ == '__main__':
    sol = Solution()
    print sol.checkPerfectNumber(6)
    print sol.checkPerfectNumber(28)
    print sol.checkPerfectNumber(1234)

    print sol.checkPerfectNumber2(28)

    print sol.checkPerfectNumber3(28)

    print sol.checkPerfectNumber3(6)