Easy

题目描述

给定一个整数 n，如果 n 恰好有三个正除数，则返回 true，否则返回 false。

如果存在整数 k 使得 n = k * m，则整数 m 是 n 的除数。

示例 1：

输入：n = 2
输出：false
解释：2 只有两个除数：1 和 2。

示例 2：

输入：n = 4
输出：true
解释：4 有三个除数：1、2 和 4。

约束条件：

  • 1 <= n <= 10^4

提示：

  • 你可以计算除数的个数，然后检查它们是否等于 3
  • 注意 n 等于 1 的情况，因为某些解法可能在此处失败

解题思路

这道题有两种主要的解题思路：

方法一：直接计数法 最直观的方法是遍历从 1 到 n 的所有数字，统计有多少个是 n 的除数。时间复杂度为 O(n)。

方法二：数学优化法（推荐） 我们可以利用数学性质优化。对于任意正整数，除数总是成对出现的，比如 n = 12，除数有 1×12, 2×6, 3×4。但当 n 是完全平方数时，√n 会被计算两次。

更进一步，我们发现只有当 n 是质数的平方时，才恰好有 3 个除数：1、质数本身、质数的平方。因此可以先判断 n 是否是完全平方数，然后检查其平方根是否为质数。

关键观察：

  • 一个数恰好有 3 个除数，当且仅当它是某个质数的平方
  • 例如：4 = 2²，除数为 1, 2, 4；9 = 3²，除数为 1, 3, 9

我们采用第二种方法，先检查是否为完全平方数，再验证平方根的质性。

代码实现

class Solution {
public:
    bool isThree(int n) {
        // 检查是否为完全平方数
        int root = sqrt(n);
        if (root * root != n) return false;
        
        // 检查平方根是否为质数
        if (root <= 1) return false;
        for (int i = 2; i * i <= root; i++) {
            if (root % i == 0) return false;
        }
        return true;
    }
};

class Solution:
    def isThree(self, n: int) -> bool:
        # 检查是否为完全平方数
        root = int(n ** 0.5)
        if root * root != n:
            return False
        
        # 检查平方根是否为质数
        if root <= 1:
            return False
        for i in range(2, int(root ** 0.5) + 1):
            if root % i == 0:
                return False
        return True

public class Solution {
    public bool IsThree(int n) {
        // 检查是否为完全平方数
        int root = (int)Math.Sqrt(n);
        if (root * root != n) return false;
        
        // 检查平方根是否为质数
        if (root <= 1) return false;
        for (int i = 2; i * i <= root; i++) {
            if (root % i == 0) return false;
        }
        return true;
    }
}

var isThree = function(n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            count++;
            if (count > 3) return false;
        }
    }
    return count === 3;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(√√n)
空间复杂度O(1)

说明：

  • 时间复杂度：计算平方根为 O(1)，判断质数需要检查到 √root，即 O(√√n)
  • 空间复杂度：只使用常数额外空间

相关题目