如何解决leetcode中完美数的问题-乐山大橙子建站

新闻中心

这里有您想知道的互联网营销解决方案

如何解决leetcode中完美数的问题

小编给大家分享一下如何解决leetcode中完美数的问题，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

在化德等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站设计、做网站网站设计制作按需开发网站,公司网站建设,企业网站建设,品牌网站制作,全网营销推广,外贸网站建设,化德网站建设费用合理。

题目链接

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

题目描述

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

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

示例：

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

注意:

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

解题方案

思路

标签：数学
首先由于完美数的定义，需要排除自身，所以数字1一定不是完美数
其次我们需要计算num除了它自身以外的所有正因子之和sum，正因子必然是成对出现的，故而我们只需要遍历到num的平方根sqrt即可

以36为例，它的非自身外正因子有，1、2、3、4、6、9、12、18，其中1和6单独计算，[2, 18]、[3, 12]、[4, 9]都是对应关系、
所以只需要遍历到36的平方根6就可以获取全部正因子
1单独计算的原因是要排除自身，6单独计算的原因是 6 * 6 = 36，两个值相同，故而只能计算一遍

时间复杂度：O(logn)，n为num的大小

Tips：完美数只有 6, 28, 496, 8128, 33550336 这几个，可以通过判断该数字是否为以下几个来解决

代码

Java版本

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

JavaScript版本

/**
* @param {number} num
* @return {boolean}
*/
var checkPerfectNumber = function(num) {
   if(num == 1) {
       return false;
   }
   let sum = 1; // 正整数一定会有一个1，同时不用考虑自身，所以单独处理
   let i = 2;
   const 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;
};