Problem Description

This problem asks you to determine whether a given integer n has exactly three positive divisors.

A divisor of n is any positive integer that divides n evenly (with no remainder). For example, if n = 12, its divisors are 1, 2, 3, 4, 6, and 12.

The task is to return true if n has exactly 3 divisors, and false otherwise.

Key observations:

• Every positive integer has at least two divisors: 1 and itself
• For a number to have exactly 3 divisors, it must have exactly one additional divisor besides 1 and itself
• This only happens when n is a perfect square of a prime number

For example:

• n = 4 has divisors {1, 2, 4} → exactly 3 divisors → return true
• n = 9 has divisors {1, 3, 9} → exactly 3 divisors → return true
• n = 12 has divisors {1, 2, 3, 4, 6, 12} → 6 divisors → return false

The solution counts how many numbers between 2 and n-1 divide n evenly. If exactly one such divisor exists (which would be the square root of n if n is a perfect square of a prime), then including 1 and n itself gives exactly 3 total divisors.

Intuition

To understand when a number has exactly three divisors, let's think about the structure of divisors.

Every positive integer n always has at least two divisors: 1 and n itself. For n to have exactly three divisors, we need exactly one more divisor.

When does this happen? Let's consider how divisors typically come in pairs. When we find a divisor d of n, we also get n/d as another divisor. For instance, if 12 is divisible by 3, then 12/3 = 4 is also a divisor. This pairing means most numbers have an even number of divisors.

The only exception is when d = n/d, which means d² = n. This happens when n is a perfect square. In this case, the square root doesn't pair with another distinct divisor.

But having a perfect square isn't enough. Consider n = 16:

• Divisors: {1, 2, 4, 8, 16}
• Even though 4² = 16, we have 5 divisors, not 3

The key insight is that for exactly 3 divisors, we need:

1. The number 1 (always present)
2. The number n itself (always present)
3. Exactly one number in between

This middle number must be the square root of n, and it must be the ONLY divisor between 1 and n. This happens when the square root is a prime number, because prime numbers have no divisors other than 1 and themselves.

Therefore, n has exactly 3 divisors if and only if n is the square of a prime number (like 4 = 2², 9 = 3², 25 = 5²).

The solution cleverly counts divisors between 2 and n-1. If this count equals 1, then that single divisor must be the prime square root, giving us exactly 3 total divisors.

Learn more about Math patterns.

Solution Approach

The solution uses a straightforward counting approach to determine if n has exactly three divisors.

Implementation Steps:

1. Count divisors between 2 and n-1: The solution iterates through all integers i from 2 to n-1 and checks if each one divides n evenly using the modulo operator (n % i == 0).

2. Use a generator expression: The code (n % i == 0 for i in range(2, n)) creates a generator that yields True for each divisor found and False otherwise.

3. Sum the boolean values: Python treats True as 1 and False as 0, so sum() effectively counts how many divisors exist between 2 and n-1.

4. Check if count equals 1: If exactly one divisor exists in the range [2, n-1], then including 1 and n itself gives exactly 3 total divisors.

Code Walkthrough:

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

• range(2, n) generates numbers from 2 to n-1
• n % i == 0 checks if i is a divisor of n
• sum(...) counts how many True values (divisors) are found
• == 1 returns True if exactly one divisor exists between 2 and n-1

Time Complexity: O(n) - we check each number from 2 to n-1

Space Complexity: O(1) - only using a constant amount of extra space

Example Trace:

• For n = 9: Check 2, 3, 4, 5, 6, 7, 8
  • Only 3 divides 9 evenly
  • Count = 1, so return True
• For n = 12: Check 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
  • 2, 3, 4, 6 all divide 12 evenly
  • Count = 4, so return False

Example Walkthrough

Let's walk through the solution with n = 9:

Step 1: Identify what we're looking for

• We need to check if 9 has exactly 3 divisors total
• We know 1 and 9 are always divisors, so we need exactly 1 more

Step 2: Check each potential divisor from 2 to 8

• i = 2: Is 9 % 2 == 0? No (9 ÷ 2 = 4 remainder 1) → Not a divisor
• i = 3: Is 9 % 3 == 0? Yes (9 ÷ 3 = 3 remainder 0) → Found a divisor!
• i = 4: Is 9 % 4 == 0? No (9 ÷ 4 = 2 remainder 1) → Not a divisor
• i = 5: Is 9 % 5 == 0? No (9 ÷ 5 = 1 remainder 4) → Not a divisor
• i = 6: Is 9 % 6 == 0? No (9 ÷ 6 = 1 remainder 3) → Not a divisor
• i = 7: Is 9 % 7 == 0? No (9 ÷ 7 = 1 remainder 2) → Not a divisor
• i = 8: Is 9 % 8 == 0? No (9 ÷ 8 = 1 remainder 1) → Not a divisor

Step 3: Count the divisors found

• We found exactly 1 divisor (the number 3) in the range [2, 8]

Step 4: Determine the result

• Since we found exactly 1 divisor between 2 and n-1, the total divisors are:
  • 1 (always a divisor)
  • 3 (the one we found)
  • 9 (n itself, always a divisor)
• Total: 3 divisors → Return true

Why this works: The number 9 = 3², where 3 is prime. Prime squares always have exactly 3 divisors: 1, the prime number itself, and the square.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The code iterates through all integers from 2 to n-1 (using range(2, n)), checking if each number is a divisor of n by computing n % i == 0. This results in n - 2 iterations, making the time complexity linear with respect to n.

Space Complexity: O(1)

The generator expression (n % i == 0 for i in range(2, n)) is evaluated lazily and consumed immediately by the sum() function. No additional data structures are created to store intermediate results. The only space used is for the loop variable i and the accumulator in sum(), both of which require constant space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Time Complexity for Large Values

The current solution has O(n) time complexity, which becomes extremely slow for large values of n. For example, if n = 10^9, the algorithm would need to check nearly a billion numbers.

Problem Example:

# This would be very slow for large n
def isThree(self, n: int) -> bool:
    return sum(n % i == 0 for i in range(2, n)) == 1

Solution: Optimize by only checking up to √n, since divisors come in pairs:

def isThree(self, n: int) -> bool:
    if n < 4:
        return False
  
    # Check if n is a perfect square
    sqrt_n = int(n ** 0.5)
    if sqrt_n * sqrt_n != n:
        return False
  
    # Check if the square root is prime
    if sqrt_n < 2:
        return False
    for i in range(2, int(sqrt_n ** 0.5) + 1):
        if sqrt_n % i == 0:
            return False
    return True

2. Edge Case: Small Values of n

The original solution doesn't explicitly handle edge cases where n < 4, though it works correctly due to the logic.

Problem Example:

# For n = 1: divisors are [1] → only 1 divisor
# For n = 2: divisors are [1, 2] → only 2 divisors
# For n = 3: divisors are [1, 3] → only 2 divisors

Solution: Add explicit edge case handling for clarity:

def isThree(self, n: int) -> bool:
    if n < 4:  # Numbers less than 4 cannot have exactly 3 divisors
        return False
    return sum(n % i == 0 for i in range(2, n)) == 1

3. Mathematical Understanding Gap

Not recognizing that only perfect squares of prime numbers have exactly 3 divisors can lead to inefficient brute-force solutions.

Why this matters:

• Perfect square of prime p: divisors are [1, p, p²]
• Any other number will have either 2 divisors (prime), 4+ divisors (composite), or an even number of divisors (non-perfect squares)

Optimized Solution Using This Property:

def isThree(self, n: int) -> bool:
    # Check if n is a perfect square
    sqrt_n = int(n ** 0.5)
    if sqrt_n * sqrt_n != n:
        return False
  
    # Check if sqrt_n is prime
    if sqrt_n <= 1:
        return False
    if sqrt_n == 2:
        return True
    if sqrt_n % 2 == 0:
        return False
  
    # Check odd divisors only
    for i in range(3, int(sqrt_n ** 0.5) + 1, 2):
        if sqrt_n % i == 0:
            return False
    return True

4. Integer Overflow/Precision Issues

When checking if n is a perfect square using floating-point arithmetic, precision errors might occur for very large numbers.

Problem Example:

# Potential precision issue
sqrt_n = n ** 0.5
if int(sqrt_n) ** 2 == n:  # May fail for large n due to float precision

Solution: Use integer-only arithmetic:

def isThree(self, n: int) -> bool:
    # Binary search for perfect square check (avoids float precision issues)
    left, right = 1, n
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        if square == n:
            # Check if mid is prime
            return self.isPrime(mid)
        elif square < n:
            left = mid + 1
        else:
            right = mid - 1
    return False

def isPrime(self, num: int) -> bool:
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True