Welcome to Subscribe On Youtube
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.
-
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; } } ############ class Solution { public boolean checkPerfectNumber(int num) { if (num == 1) { return false; } int s = 1; for (int i = 2; i * i <= num; ++i) { if (num % i == 0) { s += i; if (i != num / i) { s += num / i; } } } return s == num; } }
-
// 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: def checkPerfectNumber(self, num: int) -> bool: if num == 1: return False s, i = 1, 2 while i * i <= num: if num % i == 0: s += i if i != num // i: s += num // i i += 1 return s == num ############ 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
-
func checkPerfectNumber(num int) bool { if num == 1 { return false } s := 1 for i := 2; i*i <= num; i++ { if num%i == 0 { s += i if i != num/i { s += num / i } } } return s == num }