1952. 三除数

🟢   🔖  数学 枚举 数论  🔗 力扣 LeetCode

题目

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. 1
2. n 自身
3. 另一个不同的因子 x

因此，对于一个数 n，要使其正好只有三个因子，满足条件的数必须是 完全平方数 且其平方根是一个质数。

因为，完全平方数 n 的因子包括 1、√n 和 n，而如果 √n 是质数，因子个数正好是 3。

1. 检查 n 是否为完全平方数：
   • 计算 sqrt = √n。
   • 如果 sqrt 不是整数，直接返回 false。
2. 判断平方根是否是质数：
   • 检查 sqrt 是否仅能被 1 和自身整除。
3. 返回结果：
   • 如果 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	最小偶倍数		数学 数论	🟢	🀄️ 🔗