We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Three Divisors

Number: 2083

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Determine whether a given integer n has exactly three positive divisors. A number has exactly three divisors if and only if it is the square of a prime number, meaning its divisors are 1, the prime number, and the number itself.

Key Insights

  • A number n has exactly three divisors if it is a perfect square.
  • The square root of n must be a prime number.
  • This approach avoids checking every number up to n for divisibility.

Space and Time Complexity

Time Complexity: O(√n) in worst-case scenario when checking if the square root is prime. Space Complexity: O(1)

Solution

The solution starts by checking if n is a perfect square. If it is, compute the integer square root of n. Then, determine if this integer is a prime number by checking divisibility from 2 up to the square root of that integer. If the integer square root is prime, then n has exactly three divisors; otherwise, it does not. This solution leverages simple arithmetic and iteration while using only constant additional space.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to check if n has exactly three divisors
def is_three_divisors(n):
    # Calculate the square root of n
    sqrt_n = int(n ** 0.5)
    # Check if n is a perfect square
    if sqrt_n * sqrt_n != n:
        return False
    # Function to check if a number is prime
    def is_prime(num):
        if num < 2:
            return False
        # Iterate from 2 to the square root of num
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True
    # n has three divisors if its square root is prime
    return is_prime(sqrt_n)

# Example usage:
print(is_three_divisors(4))  # Expected output: True
print(is_three_divisors(2))  # Expected output: False
← Back to All Questions