2521-数组乘积中的不同质因数数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。

注意：

  • 质数 是指大于 1 且仅能被 1 及自身整除的数字。
  • 如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。

示例 1：

**输入：** nums = [2,4,3,7,10,6]
**输出：** 4
**解释：**
nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7 。
共有 4 个不同的质因数，所以返回 4 。

示例 2：

**输入：** nums = [2,4,8,16]
**输出：** 1
**解释：**
nums 中所有元素的乘积是：2 * 4 * 8 * 16 = 1024 = 210 。
共有 1 个不同的质因数，所以返回 1 。

提示：

  • 1 <= nums.length <= 104
  • 2 <= nums[i] <= 1000

遍历每个数，分解质因数，把质因数加到哈希表中。分解质因数的原理见 第 324 场周赛视频讲解 ，可以看看。

答案为哈希表的大小。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        s = set()
        for x in nums:
            i = 2
            while i * i <= x:
                if x % i == 0:
                    s.add(i)
                    x //= i
                    while x % i == 0:
                        x //= i
                i += 1
            if x > 1:
                s.add(x)
        return len(s)
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func distinctPrimeFactors(nums []int) int {
	set := map[int]struct{}{}
	for _, x := range nums {
		for i := 2; i*i <= x; i++ {
			if x%i == 0 {
				set[i] = struct{}{}
				for x /= i; x%i == 0; x /= i {
				}
			}
		}
		if x > 1 {
			set[x] = struct{}{}
		}
	}
	return len(set)
}

复杂度分析

  • 时间复杂度：O(n\sqrt{U})，其中 n 为 nums 的长度，U=\max(\textit{nums})。
  • 空间复杂度：O\left(\dfrac{U}{\log U}\right)。至多有 O\left(\dfrac{U}{\log U}\right) 个质因数。

相似题目

 Comments
On this page
2521-数组乘积中的不同质因数数目