又一道可以投机取巧的算法题：完美数

痛定思痛。 2023-07-21 06:28 7阅读 0赞

**点击关注上方“五分钟学算法”，**

**设为“置顶或星标”，第一时间送达干货。**

![format_png][]

转自编程如画，作者灵魂画师牧码

今天分享的题目来源于 LeetCode 第 507 号问题：完美数。这是一道标签为 **数学** 的题目，本文不仅提供一般的解题思路，同时在文章末尾分享它的 **投机取巧** 的解法。

## 一、题目链接 ##

https://leetcode-cn.com/problems/perfect-number/

## 二、题目描述 ##

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

给定一个 **整数** `n`， 如果他是完美数，返回 `True`，否则返回 `False`

**示例：**

输入: 28
    输出: True
    解释: 28 = 1 + 2 + 4 + 7 + 14

**提示：**

输入的数字 `n` 不会超过 100,000,000. (1e8)

## 三、题目分析 ##

完美数字的定义：一个整数等于除其自身之外的所有的因子之和。

由于不能包含自身，所以 n 必定大于1。

学过数学的都知道，1 是任意数字的因子，所以寻找其它因子的范围是 **\[2, sqrt(n)\]** 。

为什么是到 sqrt(n) 呢？

以数字 36 为例。

它的非自身外正因子有，1、2、3、4、6、9、12、18，其中 1 和 6 单独计算，\[2, 18\]、\[3, 12\]、\[4, 9\] 都是对应关系，所以只需要遍历到 36 的平方根 6 就可以获取全部正因子。

1单独计算的原因是要排除自身，6单独计算的原因是 6 \* 6 = 36，两个值相同，故而只能计算一遍。

## 四、图片理解 ##

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

## 五、参考代码 ##

class Solution {
        public boolean checkPerfectNumber(int num) {
            if(num == 1) {
                return false;
            }
            int sum = 1; // 正整数一定会有一个1，同时不用考虑自身，所以单独处理
            int i = 2;
            double sqrt = Math.sqrt(num);
            for(;i < sqrt;i++) {
                if(num % i == 0) {
                    sum += i;
                    sum += num / i;
                }
            }
            // 此处单独处理的原因在于只需要加1次i值，如果在循环中会加2次
            if(i * i == num) {
                sum += i;
            }
            return sum == num;
        }
    }

事实上，在题目给出的范围里面，完美数是非常上的，只有  **6, 28, 496, 8128, 33550336** 这几个，可以通过判断该数字是否为以下几个来解决。

//投机取巧的解法
    class Solution {
    public:
        bool checkPerfectNumber(int num) {
            return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
        }
    };

**END**

--------------------

![format_png 9][]

● [我这些年从来没有用过算法，除了出去面试的时候][Link 1]

[● ][Link 2][摸鱼神器，千万别让老板看见！][Link 3]

● [面试了15位来自985/211高校的2020届研究生，熬夜赶出了这篇文章][15_985_211_2020]

● [为啥SQL加了索引会使数据查找更快？][SQL]

![format_png 10][]

点“在看”你懂得

![format_png 11][]

[format_png]: /images/20230528/fdba7f3a92bf40e6a06e96c555d81031.png
[format_png 1]: /images/20230528/384f47fb952b4850ab530e2e9c3741ef.png
[format_png 2]: /images/20230528/7ac1dc5176254059b30bf964a5e7e650.png
[format_png 3]: /images/20230528/c67879e91f064ebc9a9ffb745b0bb1ec.png
[format_png 4]: /images/20230528/16d4304d3d8a43ccb880abfed2ba5b36.png
[format_png 5]: /images/20230528/4f9eb173ac144e69b630ad22ca0711c1.png
[format_png 6]: /images/20230528/f80801ef8e644438973c5fefa814fac5.png
[format_png 7]: /images/20230528/a33b7075ba1b4259ae7deaded8ed42d3.png
[format_png 8]: /images/20230528/e7b2e6d3c574431599ecbd725e101078.png
[format_png 9]: /images/20230528/9bb74b966cf0430c93c50f14c059af29.png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/105190257
[Link 2]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/105259599
[15_985_211_2020]: https://blog.csdn.net/kexuanxiu1163/article/details/105172002
[SQL]: https://blog.csdn.net/kexuanxiu1163/article/details/105236318
[format_png 10]: /images/20230528/93374f5f5bd2449bb0f76d05169554ef.png
[format_png 11]: /images/20230528/75943ef0570a45cfba07e6ec96c5af7f.png