跳至主要內容

1952. 三除数


1952. 三除数

🟢   🔖  数学 枚举 数论  🔗 力扣open in new window LeetCodeopen in new window

题目

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√nn,而如果 √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找出数组的最大公约数[✓]数组 数学 数论🟢🀄️open in new window 🔗open in new window
2413最小偶倍数数学 数论🟢🀄️open in new window 🔗open in new window