7/24 每日一題 (返回正因數之和 除了數字本身=本身)

 A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer n, return true if n is a perfect number, otherwise return false.

 

Example 1:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

Example 2:

Input: num = 7
Output: false

 

Constraints:

• 1 <= num <= 108

class Solution:

    def checkPerfectNumber(self, num: int) -> bool:

        #總和從1開始,因為所有數都能被1除

        if num == 1:

            return False

        res_sum=1

        #從2到n的平方根 ex: 4=2*2  最大到平方

        for i in range(2,int(num**0.5)+1):

            if num%i ==0:

                res_sum += i

                res_sum += num//i

        return res_sum == num

#證明 約數成對出現, 假設 n有一個約數x 那必然存在另一個約數y 使 x*y=n 其中x、y都屬於n的約數

x*y=n

如果 x <= sqrt(n)

因為, y=n//x >>>> y >= n // sqrt(n) = sqrt(n)

反之 y >= sqrt(n)

則 x=n//y >>> x <= n//sqrt(n) = sqrt(n)