Perfect Number
Perfect Number

Perfect Number
• 发表于 4个月前
• 阅读 4
• 收藏 0
• 评论 0

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)

① 第一种思路是暴力解决，但是超时了。

public class Solution {
public boolean checkPerfectNumber(int num) {
if(num <= 0) return false;
int sum = 0;
for (int i = 1;i < num ;i ++ ) {
if (num % i == 0) {
sum += i;
}
}
if (num == sum) {
return true;
}else{
return false;
}
}
}

② 根据上一个解法，我们考虑2-sqrt（nums）范围内的数，之后的就是nums/之前的数。要注意的是要考虑到i！=num / i的情况。

public class Solution { //14ms
public boolean checkPerfectNumber(int num) {
if (num == 1) return false;
int sum = 0;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) sum += num / i;
}
}
sum ++;
return sum == num;
}
}

public class Solution { //14ms
public boolean checkPerfectNumber(int num) {
if (num == 1) return false;
int sum = 0;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
sum += i + num / i;
}
}
sum ++;
return sum == num;
}
}

6 = 1 + 2 + 3
28 = 1 + 2 + 3 + 4 + 5 + 6 + 7

public class Solution { //10ms
public boolean checkPerfectNumber(int num) {
if(num <= 1) {
return false;
}
int sum = 0;
int n = num;
while(n % 2 == 0) { //可以被2整除
n /= 2;
}
sum = n * (n + 1) / 2;
return sum == num;
}
}

④ sum = 1 + 2 + ...... + 最大的不能被2整除的因子。

public class Solution { //11ms
public boolean checkPerfectNumber(int num) {
if(num == 0 || num == 1) return false;
int sum = 1;
int n = 2;
while(num % n == 0){
sum += n;
sum += num / n;
n = 2 * n;
}

return sum == num ? true : false;
}
}

×