507. Perfect Number

题目

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;
    }

Comments are closed