507. Perfect Number #

Problem #

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)

Problem Summary #

For a positive integer, if it is equal to the sum of all its positive factors excluding itself, we call it a “perfect number”. Given an integer n, if it is a perfect number, return True; otherwise, return False.

Solution Approach #

• Given an integer, determine whether this number is a perfect number. The range of the integer is less than 1e8.
• Easy problem. As described in the problem statement, first get all positive factors of this integer. If the sum of the positive factors equals the original number, then it is a perfect number.
• This problem can also be solved with a lookup table. There are actually not many perfect numbers below 1e8, only 5.

Code #

package leetcode

import "math"

// Method One
func checkPerfectNumber(num int) bool {
	if num <= 1 {
		return false
	}
	sum, bound := 1, int(math.Sqrt(float64(num)))+1
	for i := 2; i < bound; i++ {
		if num%i != 0 {
			continue
		}
		corrDiv := num / i
		sum += corrDiv + i
	}
	return sum == num
}

// Method Two: lookup table
func checkPerfectNumber_(num int) bool {
	return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336
}