Medium

题目描述

给你一个正整数数组 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 = 2^5 * 3^2 * 5 * 7 。
共有 4 个不同的质因数，所以返回 4 。

示例 2：

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

提示：

  • 1 <= nums.length <= 10^4
  • 2 <= nums[i] <= 1000

解题思路

解题思路

这道题要求找到数组所有元素乘积的不同质因数个数。关键insight是：我们不需要真的计算乘积，因为乘积会非常大而溢出。

核心思路是利用质因数分解的性质：

  • 如果 a = p1^x1 * p2^x2 * ... * pk^xk
  • 如果 b = p1^y1 * p2^y2 * ... * pk^yk
  • 那么 a * b = p1^(x1+y1) * p2^(x2+y2) * ... * pk^(xk+yk)

因此，乘积的质因数就是各个数的质因数的并集。

算法步骤：

  1. 对每个数字进行质因数分解
  2. 将所有质因数放入集合中去重
  3. 返回集合的大小

质因数分解方法：

  • 从 2 开始到 √n，如果 i 能整除 n，则 i 是质因数
  • 持续除以 i 直到不能整除，然后检查下一个数
  • 如果最后 n > 1，说明 n 本身是个质因数

时间复杂度主要取决于质因数分解，由于数字范围不超过 1000，分解效率很高。

代码实现

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_set<int> primes;
        
        for (int num : nums) {
            // 质因数分解
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    primes.insert(i);
                    while (num % i == 0) {
                        num /= i;
                    }
                }
            }
            // 如果num > 1，说明num本身是一个质因数
            if (num > 1) {
                primes.insert(num);
            }
        }
        
        return primes.size();
    }
};

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        primes = set()
        
        for num in nums:
            # 质因数分解
            i = 2
            while i * i <= num:
                if num % i == 0:
                    primes.add(i)
                    while num % i == 0:
                        num //= i
                i += 1
            # 如果num > 1，说明num本身是一个质因数
            if num > 1:
                primes.add(num)
        
        return len(primes)

public class Solution {
    public int DistinctPrimeFactors(int[] nums) {
        HashSet<int> primes = new HashSet<int>();
        
        foreach (int num in nums) {
            int current = num;
            // 质因数分解
            for (int i = 2; i * i <= current; i++) {
                if (current % i == 0) {
                    primes.Add(i);
                    while (current % i == 0) {
                        current /= i;
                    }
                }
            }
            // 如果current > 1，说明current本身是一个质因数
            if (current > 1) {
                primes.Add(current);
            }
        }
        
        return primes.Count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var distinctPrimeFactors = function(nums) {
    const primes = new Set();
    
    for (let num of nums) {
        for (let i = 2; i * i <= num; i++) {
            while (num % i === 0) {
                primes.add(i);
                num /= i;
            }
        }
        if (num > 1) {
            primes.add(num);
        }
    }
    
    return primes.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × √m)
空间复杂度O(k)

其中：

  • n 是数组长度
  • m 是数组中元素的最大值
  • k 是不同质因数的个数（最多为所有小于等于1000的质数个数，约168个）

相关题目