LeetCode - 507. Perfect Number

# LeetCode - 507. Perfect Number ###### tags: `LeetCode` `Guide` `C++` `Easy` > 原題連結: https://leetcode.com/problems/perfect-number/ > Difficulty: Easy ## 題目說明 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 1. #### Input: ``` 28 ``` #### Output: ``` True ``` #### Explanation: ``` 28 = 1 + 2 + 4 + 7 + 14 ``` #### Note: ``` The input number **n** will not exceed 100,000,000. (1e8) ``` ## 說明這題其實還蠻尷尬的，實際上不太像是在考你code，偏向數學的成分居多。總之就是要檢查**完全數**，完全數就是把這個數本身的因數(不包含自己)全部相加，最後得到的總和會正好等於自己。例如: 6的因數有1、2、3、6，因為不包含自己，所以只計算1+2+3，得到6自己，所以6就是一個完全數。題目會給一個數字，試著檢查它是不是完全數。 ## Code與解析 ### 作法1. Brute Force [Accept] [TimeLimitExceed] > Runtime: 1180 ms > faster than 26.76% > Memory: 8 MB > less than 100.00% ```cpp= class Solution { public: bool checkPerfectNumber(int num) { if(num <= 1) return false; int sum = 1; for(int i = 2; i <= num / 2; i++){ if(num % i == 0) sum += i; } return sum == num; } }; ``` 作法1是最為直觀的暴力破解，從1開始到num的一半為止(剩下的一定不是因數)全部檢查一遍，最後檢查因數總和。然而，當num本身足夠大的時候，要計算比對的次數就會激增，從而導致TLE，顯然有其他方法。 > p.s. 2020/01/03 重新上傳一次code，可以得到AC，可能把時限放寬了，但理論上應該要TLE。 ### 作法2. Optimal Solution [Accept] > Runtime: 0 ms > faster than 100.00% > Memory: 8 MB > less than 100.00% ```cpp= class Solution { public: bool checkPerfectNumber(int num) { if(num <= 1) return false; int sum = 1, i = 2; for(i = 2; i * i < num; i++){ if(num % i == 0) { sum += i; sum += num / i; } } if(i * i == num) sum += i; return sum == num; } }; ``` 與作法1不同的是，作法2的迴圈的範圍限制在了i * i < num。理由是這樣的，因為我們今天所找的是因數，基本上，因數必定是成對出現的，只有一個情況除外:i * i = num的i本身。因此如果我們確定i是因數，那num/i也一定是因數，並且只要檢查到$\sqrt {num}$即可