Code Implementation

class Solution:
    def isThree(self, n: int) -> bool:
        # A number has exactly 3 divisors if and only if it is a perfect square of a prime
        import math

        root = int(math.sqrt(n))
        if root * root != n:
            return False

        # Check if root is prime
        if root < 2:
            return False
        for i in range(2, int(root ** 0.5) + 1):
            if root % i == 0:
                return False
        return True
      

class Solution {
public:
    bool isThree(int n) {
        int root = (int)sqrt(n);
        if (root * root != n) return false;
        if (root < 2) return false;
        for (int i = 2; i * i <= root; ++i) {
            if (root % i == 0) return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean isThree(int n) {
        int root = (int)Math.sqrt(n);
        if (root * root != n) return false;
        if (root < 2) return false;
        for (int i = 2; i * i <= root; ++i) {
            if (root % i == 0) return false;
        }
        return true;
    }
}
      

var isThree = function(n) {
    let root = Math.floor(Math.sqrt(n));
    if (root * root !== n) return false;
    if (root < 2) return false;
    for (let i = 2; i * i <= root; ++i) {
        if (root % i === 0) return false;
    }
    return true;
};
      

Problem Description

Given a positive integer n, determine whether n has exactly three positive divisors. Return true if it does, and false otherwise.

• Input: A single integer n
• Output: A boolean value indicating whether n has exactly three positive divisors

Constraints:

• 1 ≤ n ≤ 10⁴
• There is only one valid answer for each input.

Thought Process

Let's start by understanding the problem: for a given integer n, we need to check if it has exactly three positive divisors. A brute-force approach would be to count all the divisors of n by iterating from 1 to n and checking which numbers divide n evenly. If the count is exactly 3, return true; otherwise, return false.

However, this brute-force approach is inefficient, especially for large values of n. Is there a mathematical property that characterizes numbers with exactly three divisors? Upon reflection, we notice that:

• Every number has at least one divisor (itself), and all numbers have at least two (1 and itself).
• If a number has exactly three divisors, what could those divisors be?
• For example, 4 has divisors 1, 2, 4. 9 has divisors 1, 3, 9. Both 4 and 9 are perfect squares of primes (2² and 3²).

This leads to the insight: a number has exactly three positive divisors if and only if it is the square of a prime number. The divisors are 1, the prime, and the square itself.

Solution Approach

Based on the mathematical insight, we can design an efficient algorithm:

1. Compute the integer square root of n. Let's call it root.
2. Check if root * root == n. If not, n is not a perfect square, so it can't have exactly three divisors.
3. Check if root is a prime number. If it is, then n is the square of a prime, and thus has exactly three divisors.
4. If root is not prime, return false.

To check if root is prime, we can use trial division up to the square root of root.

• We use trial division because it's simple and sufficient for the constraint (since n ≤ 10,000, root ≤ 100).
• This method is much faster than checking all divisors of n directly.

Example Walkthrough

Consider n = 9:

• Compute the square root: root = 3.
• Check if 3 * 3 == 9: True, so 9 is a perfect square.
• Is 3 a prime number? Yes, since its only divisors are 1 and 3.
• Therefore, 9 has exactly three divisors: 1, 3, 9.
• The function returns true.

Now, consider n = 8:

• Compute the square root: root = 2.
• Check if 2 * 2 == 8: False (2 * 2 = 4 ≠ 8).
• So, 8 is not a perfect square. The function returns false.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n), since we check every number from 1 to n to count divisors.
• Space Complexity: O(1), since we only use a counter variable.

• Time Complexity: O(√n) in the worst case, since we compute the square root and check if root is prime by testing divisibility up to √root.
• Space Complexity: O(1), as only a few variables are used.

Since n ≤ 10⁴, root ≤ 100, so the primality check is extremely fast.

Summary

The key insight for this problem is recognizing that only perfect squares of primes have exactly three divisors. This allows us to avoid brute-force divisor counting, and instead check two simple conditions: whether n is a perfect square, and whether its square root is prime. This leads to an efficient and elegant solution that works within the problem's constraints.