原文链接: https://leetcode-cn.com/problems/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 = 6
Output: true

Example 3:

Input: num = 496
Output: true

Example 4:

Input: num = 8128
Output: true

Example 5:

Input: num = 2
Output: false

 

Constraints:

• 1 <= num <= 108

中文题目

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true，否则返回 false

 

示例 1：

输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

输入：num = 6
输出：true

示例 3：

输入：num = 496
输出：true

示例 4：

输入：num = 8128
输出：true

示例 5：

输入：num = 2
输出：false

 

提示：

• 1 <= num <= 108

通过代码

官方题解

方法一：枚举

我们枚举 $n$ 的所有因数，并计算它们的和。

在枚举时，我们只需要从 $1$ 到 $\sqrt{n}$ 进行枚举。这是因为如果 $n$ 有一个大于 $\sqrt{n}$ 的因数 $x$，那么它一定有一个小于 $\sqrt{n}$ 的因数 $n / x$。因此我们可以从 $1$ 到 $\sqrt{n}$ 枚举 $n$ 的因数，当出现一个 $n$ 的因数 $x$ 时，我们还需要算上 $n / x$。此外还需要考虑特殊情况，即 $x = n / x$，这时我们不能重复计算。

代码

[sol1]
class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) {
            return false;
        }

        int sum = 1;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }

            }
        }
        return sum == num;
    }
}

复杂度分析

• 时间复杂度：$O(\sqrt{N})$。

• 空间复杂度：$O(1)$。

方法二：欧几里得-欧拉定理

欧几里得-欧拉定理告诉我们，每个偶数是完全数都可以写成

$$
2^{p-1}(2^p-1)
$$

的形式，其中 $p$ 为素数，$2^p-1$ 也是素数，称为梅森素数。

例如，前 4 个完全数可以写成如下形式：

$$
6 = 2^1 * (2^2 - 1) \
28 = 2^2 * (2^3 - 1) \
496 = 2^4 * (2^5 - 1)\
8128 = 2^6 * (2^7 - 1)
$$

由于目前奇完全数还未被发现，因此所有的完全数都可以写成上述形式。当 $n$ 不超过 $10^8$ 时，$p$ 也不会很大，因此我们只要带入最小的若干个梅森素数 $2, 3, 5, 7, 13, 17, 19, 31$（形如 $2^p - 1$ 的素数，这里 $p$ 是素数），将不超过 $10^8$ 的所有完全数计算出来即可。

代码

[sol2]
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;
    }
}

复杂度分析

• 时间复杂度：$O(1)$。

• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
31774	76024	41.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
自除数	简单