LeetCode 1952: Three Divisors (Prime-Square Characterization)

2026-04-13 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 1952MathNumber Theory

Today we solve LeetCode 1952 - Three Divisors.

Source: https://leetcode.com/problems/three-divisors/

LeetCode 1952 diagram showing that numbers with exactly three divisors are squares of prime numbers

English

Problem Summary

Given an integer n, return true if it has exactly three positive divisors; otherwise return false.

Key Insight

A number has exactly three divisors iff it is the square of a prime: divisors are 1, p, and p². So we only need to check whether n is a perfect square and whether its square root is prime.

Algorithm

- Compute r = floor(sqrt(n)).
- If r * r != n, return false.
- Check whether r is prime by trial division up to sqrt(r).
- Return that primality result.

Complexity Analysis

Time: O(sqrt(sqrt(n))) for primality test on r.
Space: O(1).

Common Pitfalls

- Brute-forcing all divisors of n; this is unnecessary work.
- Forgetting that 1 is not prime.
- Floating-point precision concerns for very large values (safe here under problem constraints).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isThree(int n) {
        int r = (int) Math.sqrt(n);
        if (r * r != n) return false;
        return isPrime(r);
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
}

func isThree(n int) bool {
    r := int(math.Sqrt(float64(n)))
    if r*r != n {
        return false
    }
    return isPrime(r)
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    for d := 2; d*d <= x; d++ {
        if x%d == 0 {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool isThree(int n) {
        int r = (int)std::sqrt(n);
        if (r * r != n) return false;
        return isPrime(r);
    }

private:
    bool isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
};

class Solution:
    def isThree(self, n: int) -> bool:
        r = int(n ** 0.5)
        if r * r != n:
            return False
        return self.is_prime(r)

    def is_prime(self, x: int) -> bool:
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True

var isThree = function(n) {
  const r = Math.floor(Math.sqrt(n));
  if (r * r !== n) return false;
  return isPrime(r);
};

function isPrime(x) {
  if (x < 2) return false;
  for (let d = 2; d * d <= x; d++) {
    if (x % d === 0) return false;
  }
  return true;
}

中文

题目概述

给定整数 n，如果它恰好有 3 个正因数则返回 true，否则返回 false。

核心思路

一个数恰好有 3 个正因数，当且仅当它是某个质数的平方：因数正好是 1、p、p²。因此只需判断 n 是否为完全平方数，且平方根是否为质数。

算法步骤

- 计算 r = floor(sqrt(n))。
- 若 r * r != n，直接返回 false。
- 判断 r 是否为质数（试除到 sqrt(r)）。
- 返回质数判断结果。

复杂度分析

时间复杂度：O(sqrt(sqrt(n)))。
空间复杂度：O(1)。

常见陷阱

- 直接枚举 n 的全部因数，计算量不必要。
- 忘记 1 不是质数。
- 在超大整数场景忽略浮点开方误差（本题约束下通常安全）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isThree(int n) {
        int r = (int) Math.sqrt(n);
        if (r * r != n) return false;
        return isPrime(r);
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
}

func isThree(n int) bool {
    r := int(math.Sqrt(float64(n)))
    if r*r != n {
        return false
    }
    return isPrime(r)
}

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    for d := 2; d*d <= x; d++ {
        if x%d == 0 {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool isThree(int n) {
        int r = (int)std::sqrt(n);
        if (r * r != n) return false;
        return isPrime(r);
    }

private:
    bool isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
};

class Solution:
    def isThree(self, n: int) -> bool:
        r = int(n ** 0.5)
        if r * r != n:
            return False
        return self.is_prime(r)

    def is_prime(self, x: int) -> bool:
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True

var isThree = function(n) {
  const r = Math.floor(Math.sqrt(n));
  if (r * r !== n) return false;
  return isPrime(r);
};

function isPrime(x) {
  if (x < 2) return false;
  for (let d = 2; d * d <= x; d++) {
    if (x % d === 0) return false;
  }
  return true;
}