0507. Perfect Number¶
题目信息¶
- 题号:
0507
- 难度:
Easy
- 主题:
正整数、真因子、因子和、完全数判定
- 原题:
- 重点:
真因子必须小于自身、只统计正因子、判断因子和是否恰好等于原数
题目重述¶
给定正整数 num。若 num 的所有正真因子之和恰好等于 num,则称它为完全数。真因子是能够整除 num 且严格小于 num 的正整数。
判断 num 是否为完全数并返回布尔值。num 位于 [1, 10^8];数字本身不能计入因子和,1 没有除自身之外的正因子,因此不是完全数。
自建示例¶
较大的完全数:
输入:num = 496
输出:true
解释:496 的正真因子为 1、2、4、8、16、31、62、124、248,它们的和为 496。
因子和超过原数:
输入:num = 12
输出:false
解释:12 的正真因子 1、2、3、4、6 之和为 16,不等于 12。
成对枚举到平方根¶
1 是所有大于 1 的正整数的真因子,先把它加入和。对于每个除数 d,若 d 整除 num,则 num / d 也是因子;二者成对出现,只需枚举到平方根,并在完全平方数时避免把平方根加两次。
C++ 实现¶
class Solution {
public:
bool checkPerfectNumber(int num) {
if (num <= 1) return false;
long long sum = 1;
for (long long divisor = 2;
divisor * divisor <= num; ++divisor) {
if (num % divisor != 0) continue;
sum += divisor;
long long paired = num / divisor;
if (paired != divisor) sum += paired;
}
return sum == num;
}
};
代码分析¶
除数和商覆盖了除 1 与自身之外的全部正真因子,平方根的重复由条件排除;若累计和超过 num 也不会成为完全数,但完整求和仍保持逻辑直接。时间复杂度为 O(sqrt(num)),额外空间复杂度为 O(1)。