algoadvance

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m has exactly three positive divisors if and only if it is equal to the square of a prime number. For example, 9 has exactly three divisors: 1, 3, and 9.

Clarifying Questions

  1. What is the range of the input n?
    • The input n will be a positive integer, but knowing the upper limit can help in optimizing the solution.
  2. Are there any time constraints for solving this problem?
    • Typically, a solution should run within a reasonable time fitting the constraints of competitive coding (usually a few seconds at most).

By default, we will assume typical constraints, such as (1 \leq n \leq 10^9).

Strategy

To solve this problem, let’s follow these steps:

  1. Check if n is a perfect square. If n is not a perfect square, it cannot have exactly three divisors.
  2. If n is a perfect square, check if the square root of n is a prime number.
  3. If both conditions are met, return true; otherwise, return false.

Steps:

  1. Check if n is a perfect square:
    • Compute the integer square root of n (let’s call it root), using math.isqrt(n).
    • Verify if root * root == n.
  2. Check if root is a prime number:
    • Iterate over possible divisors from 2 to (\sqrt{root}).
    • If root has any divisor other than 1 and itself, then it is not a prime.

Let’s implement this strategy in Python.

Code

import math

def isThree(n: int) -> bool:
    # Step 1: Check if `n` is a perfect square
    root = int(math.isqrt(n))
    if root * root != n:
        return False
    
    # Step 2: Check if `root` is a prime number
    if root <= 1:
        return False
    for i in range(2, int(math.isqrt(root)) + 1):
        if root % i == 0:
            return False
    
    return True

# Example Usage:
print(isThree(9))  # Output should be True (divisors are 1, 3, 9)
print(isThree(10)) # Output should be False (divisors are 1, 2, 5, 10)
print(isThree(25)) # Output should be True (divisors are 1, 5, 25)

Time Complexity

Given the operations involved, the overall time complexity is (O(\sqrt[4]{n})). This is efficient and should work well within typical constraints.

Try our interview co-pilot at AlgoAdvance.com