leetcode507. 完美数

题目描述

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

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

示例 1：

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

输入：num = 7 输出：false

提示：

1 <= num <= 108

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/perfect-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

计算所有因数之和\

1. 从2到i(i*i<=num)的所有能整除的数字相加
2. 因数的另一半num/i相加
3. 当i*i==num时只加一次,最后对比和与num是否相同

• 时间复杂度(O(n))
• 空间复杂度(O(1))

法2

数学
在0-10^8中只有6,28,496,8128,33550336为完全数

• 时间复杂度(O(1))
• 空间复杂度(O(1))

执行结果

法1

func checkPerfectNumber(num int) bool {
    if num==1{return false}
 t, i := 1, 2
 for ; i*i < num; i++ {//计算i*i<num的所有因数之和
  if num%i == 0 {
   t += i + num/i
  }
 }
 if i*i == num {//特殊情况
  t += i
 }
 return t == num
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 93.85% 的用户 通过测试用例： 98 / 98

法2

func checkPerfectNumber(num int) bool {
    return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336
}