2. Using Square Root to Check Perfect Number in Java
An optimization to the loop method for checking perfect numbers involves using the square root of the number. This approach significantly reduces the number of iterations required, as you only check up to the square root of the number instead of the number itself.
Implementation in Java:
Java
public class PerfectNumberOptimized {
public static boolean isPerfect(int number) {
int sum = 1; // Start sum at 1 because 1 is a divisor for all numbers
// Loop from 2 to the square root of number
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
sum += i; // Add the divisor
if (i != number / i) {
sum += number / i; // Add the corresponding divisor greater than the square root
}
}
}
// Check if the sum of divisors is equal to the number
return number > 1 && sum == number;
}
public static void main(String[] args) {
int testNumber = 28;
if (isPerfect(testNumber)) {
System.out.println(testNumber + " is a perfect number.");
} else {
System.out.println(testNumber + " is not a perfect number.");
}
}
}

You can also try this code with Online Java Compiler
Run Code
Output
28 is a perfect number.
In this implementation, the isPerfect method starts with a sum initialized at 1. It then iterates from 2 up to the square root of the target number, checking if each number is a divisor. If it is, the divisor is added to the sum. Additionally, the corresponding divisor greater than the square root (calculated as number / i) is also added unless it's the same as the smaller divisor. This helps in accounting for all divisors without iterating through every single number up to the target.
3. Recursive Approach to Check Perfect Number in Java
A recursive method can also be used to determine if a number is perfect. This approach breaks down the problem into smaller, manageable parts by repeatedly calling the function within itself. Here, we adapt the idea of checking for divisors recursively, summing them up, and comparing the sum to the original number.
Here's how you can implement this recursively in Java:
Java
public class PerfectNumberRecursive {
// Helper function to find divisors & sum them recursively
private static int sumDivisors(int number, int i) {
// Base case: if i is equal to number, return 0
if (i == number) {
return 0;
} else if (number % i == 0) {
return i + sumDivisors(number, i + 1); // Add i if it is a divisor
} else {
return sumDivisors(number, i + 1); // Continue to next i if not a divisor
}
}
// Function to check if number is perfect
public static boolean isPerfect(int number) {
// Call recursive helper starting with 1
int sum = sumDivisors(number, 1);
return sum == number;
}
public static void main(String[] args) {
int testNumber = 28;
if (isPerfect(testNumber)) {
System.out.println(testNumber + " is a perfect number.");
} else {
System.out.println(testNumber + " is not a perfect number.");
}
}
}

You can also try this code with Online Java Compiler
Run Code
Output
28 is a perfect number.
In this code, the sumDivisors method is used to recursively find and sum all divisors of the given number, except the number itself. It starts from 1 and continues to the number-1. If the current index (i) divides the number without a remainder, it is added to the sum. The recursion continues by increasing i until it equals the number.
Time and Space Complexity
Understanding the time & space complexity of algorithms is crucial when assessing their efficiency. Let's analyze the complexities of the three methods we discussed for checking if a number is perfect in Java.
Using Loop to Check Perfect Number
-
Time Complexity: The time complexity of this method is O(n), where n is the number being checked. This is because the algorithm iterates through all numbers from 1 to n-1 to find the divisors.
- Space Complexity: The space complexity is O(1), as the method uses a constant amount of space regardless of the input size.
Using Square Root to Check Perfect Number
-
Time Complexity: This method improves the time complexity to O(√n) by only iterating up to the square root of the number. It's more efficient because it reduces the number of iterations needed to find the divisors.
- Space Complexity: The space complexity remains O(1), similar to the loop method, as it uses a fixed amount of extra space.
Recursive Approach to Check Perfect Number
-
Time Complexity: The recursive method also has a time complexity of O(n) because, in the worst case, it needs to check each number up to n-1 for divisibility.
- Space Complexity: The space complexity can increase to O(n), especially in cases where the recursion depth approaches n, because each recursive call adds a layer to the call stack.
Frequently Asked Questions
What is a perfect number?
A perfect number is a positive integer that is equal to the sum of its proper divisors, excluding the number itself. For example, 6 is perfect because its divisors are 1, 2, and 3, and 1 + 2 + 3 = 6.
Why use the square root method to check for perfect numbers?
Using the square root method reduces the number of calculations significantly, as it only requires checking up to the square root of the number. This makes the process faster especially for larger numbers.
Can the recursive method be optimized further for performance?
While the recursive method is elegant, it is generally not as efficient due to its high space complexity. Optimizing it might involve limiting recursion depth or switching to an iterative approach to reduce stack usage.
Conclusion
In this article, we have learned various methods to check if a number is a perfect number in Java. We explored a straightforward loop method, an optimized approach using square roots, and a recursive method. We discussed the pros & cons of each, especially in terms of their time and space complexity.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.