Skip to content

1952. Three Divisors 👍

  • Time: $O(\sqrt[4]{n})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  bool isThree(int n) {
    if (n == 1)
      return false;
    // The numbers with exactly three divisors are perfect squares of a prime
    // number.
    const int root = sqrt(n);
    return root * root == n && isPrime(root);
  }

 private:
  bool isPrime(int num) {
    for (int i = 2; i <= sqrt(num); ++i)
      if (num % i == 0)
        return false;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public boolean isThree(int n) {
    if (n == 1)
      return false;
    // The numbers with exactly three divisors are perfect squares of a prime
    // number.
    final int root = (int) Math.sqrt(n);
    return root * root == n && isPrime(root);
  }

  private boolean isPrime(int num) {
    for (int i = 2; i <= Math.sqrt(num); ++i)
      if (num % i == 0)
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def isThree(self, n: int) -> bool:
    if n == 1:
      return False
    # The numbers with exactly three divisors are perfect squares of a prime
    # number.
    root = math.isqrt(n)
    return (root**2 == n and
            all(root % i != 0
                for i in range(2, math.isqrt(root) + 1)))