☀（day37）

目录

题目：

题目分析：

解题思路：

解法一：常规解法

代码实现

✨代码注释

解法二：总结法

代码实现

前言：

文章中题目分析主要说明题目的隐含意，一些定义的释义。解题思路含有是代码实现的理论分析

题目：

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

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。（1 <= num <= 108）

⭐示例 1：

输入：n = 28

输出：true

解释说明：

1*28 = 28 ，2*14 = 28， 4*7 = 28， 7*4 = 28，14*2 = 28

1+2+4+7+14 = 28.

1, 2, 4, 7, 和 14 是 28 的所有正因子。

⭐示例 2：

输入：n = 7

输出：false

解释说明：

1*7 = 7 ， 1不等于7

题目分析：

题中正因子是个专有名词，通俗来讲就是一个数n的除数，这个除数满足n%除数=0.

解题思路：

解法一：常规解法

解题关键是找到数n的所有正因子。

在例1，我们看到2*14 = 14*2 =28，2和14是28的正因子。 4*7 = 7*4 = 28，4和7是28的正因子.

那么当我们找到正因子2和4时，我们用28/2，28/4，即可得到正因子14和7.

值得注意的是如果这时再用28/7 = 4，那么将得到一个重复的正因子，我们把所有正因子累加后这个重复的正因子就会影响是否为完美数的判断。

那么我们什么时候停止使用数n/正因子这一步骤呢？

设数n有正因子d1，d2。

由数n/d1 = d2可知，当d1 = d2时使用数n/正因子这一做法就会得到重复正因子

那么d1*d2 = d1*d1 = n。

我们得出结论：当得到一个正因子d时

1.如果d < 

那么可以使用n/d得出另一个正因子

2.如果d <= 

那么就停止使用n/d求另一个正因子

代码实现

def checkPerfectNumber(n):
    if n == 1:
        return False

    sum = 1
    d = 2
    while d * d <= n:
        if n % d == 0:
            sum += d
            if d * d < n:
                sum += n / d
        d += 1
    return sum == n

✨代码注释

def checkPerfectNumber(n):
    # 1肯定不是完美数
    if n == 1:
        return False

    sum = 1  # sum用于累加所有正因子，每个数的正因子都包含1所以初始化sum=1
    d = 2  # sum已经初始化为1，所以d从2开始
    while d * d <= n:  # 判断是否可以进行n/正因子求另一个正因子
        if n % d == 0:  # 判断是否满足正因子的定义
            sum += d  
            if d * d < n:  # 使用n/正因子求另一个正因子
                sum += n / d
        d += 1
    return sum == n

解法二：总结法

根据欧几里得-欧拉定理，每个偶完全数都可以写成2^{p-1}(2^p-1)的形式，其中 p为素数且 2^p-1为素数。

由于目前奇完全数还未被发现，因此题目范围 [1,10^8]内的完全数都可以写成上述形式。

再[1,10^8]内的完美数一共有如下 55 个：

6, 28, 496, 8128, 33550336

代码实现

def checkPerfectNumber(self, num: int) -> bool:
    return num == 6 or num == 28 or num == 496 or num == 8128 or num == 33550336

今天就到这，明天见。

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄