Sponsored
Sponsored
The main idea is that divisors come in pairs, and for each pair (d, n/d), if d is less than the square root of n, then d and n/d are both divisors of n. This approach allows us to only iterate up to the square root of n, making it more efficient.
Time Complexity: O(sqrt(n))
Space Complexity: O(1)
1#include <stdbool.h>
2#include <math.h>
3
4bool isPerfectNumber(int num) {
5 if (num <= 1) return false;
6 int sum = 1;
7 int sqrtNum = (int)sqrt(num);
8 for (int i = 2; i <= sqrtNum; i++) {
9 if (num % i == 0) {
10 sum += i;
11 if (i != num / i) sum += num / i;
12 }
13 }
14 return sum == num;
15}The function first checks if num is less than or equal to 1, returning false if so, as there's no perfect number <= 1. Then it initializes sum with 1 since 1 is a divisor of every number except itself. We iterate through possible divisors up to the square root of num. If i is a divisor, we add it and its pair num/i to sum, avoiding double counting. Finally, we check if sum equals num.
This approach calculates the sum of all divisors excluding the number itself by checking each integer from 1 to n-1 to determine if it's a divisor, then sums these and checks if the sum equals n. This method is simple but inefficient for large numbers.
Time Complexity: O(n)
Space Complexity: O(1)
1def checkPerfectNumber(In Python, the simplicity of this method is evident as it loops through potential divisors, calculating their total and making a comparison against the input value.