Solution Explanation

The problem asks to determine if a given integer n has exactly three divisors. A number has exactly three divisors if and only if it is the square of a prime number. This is because the divisors of a number n = p^2 (where p is a prime number) are 1, p, and p^2.

Both solutions presented efficiently address this problem, although with slightly different approaches.

Solution 1: Direct Counting

This solution iterates from 2 up to n-1, counting the number of divisors. If the count is exactly 1, it means the number has only one divisor besides 1 and itself (which is its square root), implying it's the square of a prime.

Code (Python):

class Solution:
    def isThree(self, n: int) -> bool:
        return sum(n % i == 0 for i in range(2, n)) == 1

Explanation:

• sum(n % i == 0 for i in range(2, n)): This part iterates through numbers from 2 to n-1 and checks if each number is a divisor of n. The sum() function counts the number of divisors found.
• == 1: It checks if the count of divisors (excluding 1 and n) is equal to 1. If it is, it implies the number is a perfect square of a prime.

Time Complexity: O(n) - The loop iterates up to n. Space Complexity: O(1) - Constant extra space is used.

Solution 2: Optimized Counting

This solution cleverly optimizes the divisor counting. It iterates only up to the square root of n. For each divisor i found, it also implicitly identifies another divisor (n/i). If i equals n/i, then it's a perfect square, and we only count it once.

Code (Python):

class Solution:
    def isThree(self, n: int) -> bool:
        cnt = 0
        i = 1
        while i <= n // i:
            if n % i == 0:
                cnt += 1 if i == n // i else 2
            i += 1
        return cnt == 3

Explanation:

• while i <= n // i:: The loop iterates up to the square root of n.
• if n % i == 0:: This checks if i is a divisor of n.
• cnt += 1 if i == n // i else 2: This line adds 1 to cnt if i is a perfect square (meaning i equals n/i) otherwise, it adds 2 because it finds two divisors (i and n/i).
• return cnt == 3: Returns True only if exactly 3 divisors are found (1, the prime number, and its square).

Time Complexity: O(√n) - The loop iterates up to the square root of n. Space Complexity: O(1) - Constant extra space is used.

Both solutions achieve the same result, but Solution 2 is significantly more efficient for larger values of n due to its better time complexity. The other languages (Java, C++, Go, JavaScript) implement similar logic with minor syntactic differences.