Perfect numbers are a classical concept in number theory, and understanding them can be both intriguing and insightful. On Leetcode, the Perfect Number problem challenges you to apply the foundational concept of perfect numbers in a programming context. In this extensive article, we will dissect the Perfect Number problem, comprehend the mathematics behind it, and explore various approaches to solving it using Python.
The Perfect Number problem on Leetcode is described as:
A perfect number is a positive integer that is equal to the sum of its proper divisors (positive divisors excluding itself). Given an integer
n is a perfect number, otherwise return
Input: 28 Output: True Explanation: 28 = 1 + 2 + 4 + 7 + 14
Approach 1: Basic Iteration through Divisors
The naive approach is to iterate through numbers from 1 to
n-1 and sum up the divisors of
n. Then, we can check if the sum is equal to
Here’s the Python code for this approach.
def checkPerfectNumber(num): if num <= 1: return False sum_divisors = 0 for i in range(1, num): # If i is a divisor of num if num % i == 0: sum_divisors += i return sum_divisors == num
This approach is straightforward but not efficient. It has a time complexity of O(n) since we’re iterating through all numbers less than
Approach 2: Optimization by Reducing Search Space
We can optimize our search for divisors by noting that if
d is a divisor of
n/d is also a divisor. Hence, we only need to search for divisors up to the square root of
def checkPerfectNumber(num): if num <= 1: return False sum_divisors = 1 for i in range(2, int(num ** 0.5) + 1): if num % i == 0: sum_divisors += i if i != num // i: sum_divisors += num // i return sum_divisors == num
This approach reduces the time complexity to O(√n), which is a significant improvement over the basic approach for large numbers.
Approach 3: Utilizing the Euclidean Formula for Perfect Numbers
Euclid proved that if
2^(p−1)(2^p − 1) is an integer, then it is a perfect number. Later, Euler proved that every even perfect number is of that form. This is known as the Euclidean Formula for perfect numbers. We can use this formula to check if a number is perfect without checking all its divisors.
def checkPerfectNumber(num): # The first six primes for Euclidean formula primes = [2, 3, 5, 7, 13, 17] for p in primes: perfect_number = (2 ** (p - 1)) * ((2 ** p) - 1) if perfect_number == num: return True return False
This approach has a constant time complexity, O(1), as it only checks a fixed number of perfect numbers derived from the Euclidean formula.
In this comprehensive article, we delved into the Perfect Number problem on Leetcode and explored three distinct approaches to solving it using Python. We began with the naive approach and iteratively optimized it. Ultimately, we employed a mathematical formula to achieve constant time complexity.