Leetcode No.4( 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 + 14Note: The input number n will not exceed 100,000,000. (1e8)
想法: 這題直覺很簡單,就是暴力破解,然後加上點改善。但是要達到好成績應該是要配合數學解法,數學解法就等著看答案。
一開始我先簡單寫個暴力搜尋,然後改進方法是想到一個dividor必定搭配另一個divisor,若由小而大找上去,那另一邊的divisor會由大到小。
ex: 1000= 2 * 500 = 4 *250 = ….
所以我可以在找到 2 的時候就找到 500,並且把搜尋範圍從 2~999 變成 2~499,以此類推。
這題有另外兩個陷阱就是
(1) 1 不是 perfect number
(2) 3 * 3 = 9; 3只能計算一次。這個我忽略掉了,但是答案還是對的,大概剛好沒出現這種特例。
class Solution {
public:
bool checkPerfectNumber(int num) {
if(num == 1) return false;
int remain = sqrt(num) + 1;
int sum = 1;
for (int i = 2; i < remain; i++){
if (num % i == 0) {
int result = num / i;
if (result < remain)
remain = result;
if (result == i) {
result = 0;
}
sum = sum + i + result;
}
}
if (sum == num)
return true;
else
return false;
}
};
網路上解答:
這裡有兩個加速的方法,各自獨立,其中一個就是數學上的解法,超快。
(1) 搜尋範圍只要到 squr(num) 就好了,因為
squr(num) * squr(num) = num; 雖然我自己的方法也可以減少搜尋範圍,但是遇到質數或者因數很少的數字就沒什麼效果。並且開根號的搜尋範圍還是比我的最佳狀況還少。
(2) 數學方法: 這邊我就直接貼網路上面的解答和連結。方法就是數學公式,並且這公式和值數有關,所以差不多是 hard code (因為有限定 input 範圍)
Euclid proved that 2^(p−1)(2^p−1) is an even perfect number whenever 2^p−1 is prime, where p is prime.
翻譯:
2^(p−1)(2^p−1) 是 perfect number 當 2^p−1是質數,其中p也必須是質數
這個等式是若且維若。
public class Solution {
public int pn(int p) {
return (1 << (p — 1)) * ((1 << p) — 1);
}
public boolean checkPerfectNumber(int num) {
int[] primes=new int[]{2,3,5,7,13,17,19,31};
for (int prime: primes) {
if (pn(prime) == num)
return true;
}
return false;
}
}
參考連結:
https://zh.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E6%95%B0
