1952. 三除数
1952. 三除数
题目
Given an integer n
, return true
if n
hasexactly three positive divisors. Otherwise, return false
.
An integer m
is a divisor of n
if there exists an integer k
such that n = k * m
.
Example 1:
Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.
Example 2:
Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.
Constraints:
1 <= n <= 10^4
题目大意
给你一个整数 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
解题思路
我们需要判断一个整数 n
是否有且只有三个正整数因子。这意味着 n
的因子必须是:
1
n
自身- 另一个不同的因子
x
因此,对于一个数 n
,要使其正好只有三个因子,满足条件的数必须是 完全平方数 且其平方根是一个质数。
因为,完全平方数 n
的因子包括 1
、√n
和 n
,而如果 √n
是质数,因子个数正好是 3。
- 检查
n
是否为完全平方数:- 计算
sqrt = √n
。 - 如果
sqrt
不是整数,直接返回false
。
- 计算
- 判断平方根是否是质数:
- 检查
sqrt
是否仅能被1
和自身整除。
- 检查
- 返回结果:
- 如果
n
是完全平方数且sqrt
是质数,则返回true
;否则返回false
。
- 如果
复杂度分析
- 时间复杂度:
O(√√n)
,需要判断sqrt = √n
是否为质数,时间复杂度约为O(√√n)
。 - 空间复杂度:
O(1)
,仅使用常量空间。
代码
/**
* @param {number} n
* @return {boolean}
*/
var isThree = function (n) {
const sqrt = Math.sqrt(n);
if (!Number.isInteger(sqrt)) return false; // 检查是否为完全平方数
// 判断平方根是否是质数
for (let i = 2; i * i <= sqrt; i++) {
if (sqrt % i === 0) return false; // 如果能被其他数整除,则不是质数
}
return sqrt > 1; // 1 不是质数
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
1979 | 找出数组的最大公约数 | [✓] | 数组 数学 数论 | 🟢 | 🀄️ 🔗 |
2413 | 最小偶倍数 | 数学 数论 | 🟢 | 🀄️ 🔗 |