LeetCode 507. Perfect Number
Created at 2017-12-21 Updated at 2018-01-21 Category LeetCode
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.
Note: The input number n will not exceed 100,000,000. (1e8)
You will get TLE(Time Limit Exceeded) if you simply loop all the values. So, to tackle this problem, there is a theorem that is: if number n is not a prime, there must be a factor d among the range of 2 and sqrt(n), the factor d is very important for none-prime numbers.
Just check every i from 1 to sqrt(num). When num % i == 0, we add both i and num//i to our result. And remember to exclude the num itself and check if we added a duplicate sqrt(num) in the end.