LeetCode Perfect Number

LeetCode Perfect Number

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)


判断一个数是否是完美数。完美数的定义是:一个正数,它等于它的所有不包括自己正因子数之和。比如28的所有不包括自己的正因子数有1,2,4,7,14,加起来正好等于28,所以28是一个完美数。

判断的方法也简单,因子i从1~sqrt(num),判断i是否是num的因子,如果是,则把i和num/i都加到结果里。最后判断结果是否等于num。

需要说明两点。一是循环只需进行到sqrt(num),因为大于sqrt(num)的因子可以由小于sqrt(num)的因子被num除得到,比如num=a*b,且a<b,则遍历到a时,如果num%a==0,则num/a就是b。二是注意要排除num自己这个因子,所以当a=1时,就不加num/a了。

代码如下:

class Solution {
public:
	bool checkPerfectNumber(int num) {
		if (num <= 1)return false;
		int ans = 0, n = sqrt(num);
		for (int i = 1; i <= n; ++i) {
			if (num%i == 0) {
				ans += i;
				if (i != 1 && num / i != i)ans += num / i;
			}
		}
		return ans == num;
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *