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

Three Divisors

Difficulty: Easy

Problem Description

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

Key Insights

A number has exactly three positive divisors if it is the square of a prime number.
The three divisors in this case will be 1, the prime number itself, and its square.
Therefore, the problem reduces to checking if n is a perfect square and if the square root of n is a prime number.

Space and Time Complexity

Time Complexity: O(√n) - to check for primality of the square root. Space Complexity: O(1) - no additional space required.

Solution

To solve this problem, we can use the following steps:

Calculate the integer square root of n.
Check if the square of this integer root equals n (to confirm it's a perfect square).
Check if this integer root is a prime number.
If both conditions are satisfied, n has exactly three divisors; otherwise, it does not.

We will use a simple method to check for primality, iterating through possible divisors up to the square root of the integer root.

Code Solutions

import math

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def is_three_divisors(n):
    root = int(math.sqrt(n))
    return root * root == n and is_prime(root)

← Back to All Questions