How do I avoid multiplying large numbers in this problem?

Instead of multiplying all the numbers together, use prime factorization for each element and store the distinct prime factors in a set.

What is the best way to factorize numbers in this problem?

Using the Sieve of Eratosthenes to precompute the smallest prime factor for each number helps factorize numbers efficiently.

How do I handle repeated prime factors?

By using a hash set, you automatically ensure that only distinct prime factors are counted.

Can the array size affect performance?

Yes, larger arrays may require more time for scanning, but the sieve precomputation significantly speeds up factorization for each element.

What if the numbers in the array are large?

The sieve of Eratosthenes helps efficiently handle prime factorization for numbers up to 1000, which is the upper limit in this problem.

#2521

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中不同质因数的数目。注意：质数是指大于 1 且仅能被 1 及自身整除的数字。如果 val2 / val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。示例 1：输入： nums = […

数组哈希表数学数论

题目描述

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

示例 2：

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

提示：

1 <= nums.length <= 10⁴
2 <= nums[i] <= 1000

lightbulb

解题思路

方法一：哈希表 + 质因数分解

对于数组中的每个元素，先对其进行质因数分解，然后将分解出的质因数加入哈希表中。最后返回哈希表的大小即可。

时间复杂度 $O(n \times \sqrt{m})$ ，空间复杂度 $O(\frac{m}{\log m})$ ，其中 $n$ 和 $m$ 分别为数组的长度和数组中元素的最大值。

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 n in nums:
            i = 2
            while i <= n // i:
                if n % i == 0:
                    s.add(i)
                    while n % i == 0:
                        n //= i
                i += 1
            if n > 1:
                s.add(n)
        return len(s)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate shows understanding of prime factorization methods.
question_mark
Candidate leverages hash sets effectively to store distinct factors.
question_mark
Candidate avoids directly multiplying large numbers, adhering to the problem's constraints.

warning

常见陷阱

外企场景

error
Directly multiplying the array elements, causing integer overflow or excessive computation time.
error
Failing to handle repeated prime factors correctly and undercounting them.
error
Not using efficient prime factorization methods like the Sieve of Eratosthenes, leading to slower solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider an array of larger size or numbers near the upper constraint limit.
arrow_right_alt
Extend to handle cases where the array contains numbers with repeated prime factors.
arrow_right_alt
Optimize for scenarios where many numbers share common prime factors.

help

常见问题

外企场景

继续练习

#2584 分割数组使乘积互质 #2748 美丽下标对的数目 #2001 可互换矩形的组数