题目
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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/perfect-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我的题解
public boolean checkPerfectNumber(int num) {
if(num == 1) return false;
int sum = 1, m = num;
for(int i=2;i<m;i++){
if(num%i==0){
sum += i;
m = num / i;
sum += m;
}
}
return sum == num;
}
执行用时: 404 ms, 在所有 Java 提交中击败了40.64% 的用户
内存消耗: 35.4 MB, 在所有 Java 提交中击败了 5.03% 的用户
通过测试用例:98 / 98
修改之后
public boolean checkPerfectNumber(int num) {
if(num == 1) return false;
int sum = 1, i=2;
double sqrt = Math.sqrt(num);
for(;i < sqrt ;i++){
if(num%i==0){
sum += i + num / i;
}
}
if(i*i == num) sum += i;
return sum == num;
}
执行用时:1 ms, 在所有 Java 提交中击败了92.45%的用户
内存消耗:35.5 MB, 在所有 Java 提交中击败了5.03%的用户
第一个解没有考虑到两个地方:
- i>num的平方根即可不用计算
- i*i == num ,即num的平方根为相等的整数; 之所以通过是因为满足条件的完美数没有两个平方根是相等的情况
官方题解
public boolean checkPerfectNumber(int num) {
if (num == 1) {
return false;
}
int sum = 1;
for (int d = 2; d * d <= num; ++d) {
if (num % d == 0) {
sum += d;
if (d * d < num) {
sum += num / d;
}
}
}
return sum == num;
}
执行用时: 1 ms, 在所有 Java 提交中击败了92.45% 的用户
内存消耗:35.3 MB, 在所有 Java 提交中击败了12.50% 的用户
官方题解2 – 直接从完美数上做文章
public boolean checkPerfectNumber(int num) {
return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
}
