Leetcode No.4( Perfect Number) 心得

ChingYuanYang
Aug 23, 2017 · 4 min read

題目:

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)

想法: 這題直覺很簡單,就是暴力破解,然後加上點改善。但是要達到好成績應該是要配合數學解法,數學解法就等著看答案。

一開始我先簡單寫個暴力搜尋,然後改進方法是想到一個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

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade