Formatted question description: https://leetcode.ca/all/507.html

507. Perfect Number (Easy)

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)

Related Topics:
Math

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/perfect-number/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 0, end = sqrt(num);
        for (int i = 1; i <= end; ++i) {
            if (num % i) continue;
            int j = num / i;
            sum += i;
            if (j != i && j != num) sum += j;
        }
        return sum == num;
    }
};

Java

  • class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 0)
            return false;
        int[][] primeFactorization = primeFactorize(num);
        long factorsSum = 1;
        for (int[] primePower : primeFactorization) {
            int prime = primePower[0], power = primePower[1];
            long primeSum = 0;
            long factor = 1;
            for (int i = 0; i <= power; i++) {
                primeSum += factor;
                factor *= prime;
            }
            factorsSum *= primeSum;
        }
        return factorsSum == (long) (2 * num);
    }

    public int[][] primeFactorize(int num) {
        List<Integer> primes = new ArrayList<Integer>();
        List<Integer> powers = new ArrayList<Integer>();
        if (num % 2 == 0) {
            primes.add(2);
            int power2 = 0;
            while (num % 2 == 0) {
                num /= 2;
                power2++;
            }
            powers.add(power2);
        }
        int prime = 3;
        while (num > 1) {
            if (num % prime == 0) {
                primes.add(prime);
                int power = 0;
                while (num % prime == 0) {
                    num /= prime;
                    power++;
                }
                powers.add(power);
            }
            prime += 2;
        }
        int length = primes.size();
        int[][] primeFactorization = new int[length][2];
        for (int i = 0; i < length; i++) {
            primeFactorization[i][0] = primes.get(i);
            primeFactorization[i][1] = powers.get(i);
        }
        return primeFactorization;
    }
}

  • // OJ: https://leetcode.com/problems/perfect-number/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
    bool checkPerfectNumber(int n) {
        if (n == 1) return false;
        int sum = 0;
        for (int i = 1; i * i <= n; ++i) {
            if (n % i) continue;
            sum += i;
            if (i != 1 && n / i != i) sum += n / i;
            if (sum > n) return false;
        }
        return sum == n;
    }
};

  • class Solution(object):
  def checkPerfectNumber(self, num):
    """
    :type num: int
    :rtype: bool
    """
    ans = 1
    div = 2
    while div ** 2 <= num:
      if num % div == 0:
        ans += div
        ans += num / div
      div += 1
    return ans == num if num != 1 else False

All Problems

All Solutions