## 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.");

}

}

}

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.");

}

}

}

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.