class Solution {
public:
int distinctPrimeFactors(vector<int>& nums) {
}
};
2521. 数组乘积中的不同质因数数目
给你一个正整数数组 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 <= 1042 <= nums[i] <= 1000原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 6.1 MB, 提交时间: 2023-01-03 11:46:06
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)
}
python3 解法, 执行用时: 136 ms, 内存消耗: 16.1 MB, 提交时间: 2023-01-03 11:45:51
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)