难度: 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 = 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运行时间: 36 ms
内存: 17.0 MB
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)
while x % i == 0:
x //= i
i += 1
if x > 1:
s.add(x)
return len(s)
该题解通过遍历数组中每个元素，使用试除法找出每个元素的所有质因数，并将这些质因数存储在集合中，以去除重复的质因数。最终，返回集合中元素的数量，即不同质因数的数目。试除法从2开始，直到sqrt(x)，检查是否能整除x。如果可以，将该因数加入集合，并将x除以该因数直至不再能整除。如果在结束内层循环后x大于1，则x本身是一个质数，也将其加入集合。
时间复杂度: O(n * sqrt(m))
空间复杂度: O(u)
class Solution:
def distinctPrimeFactors(self, nums: List[int]) -> int:
s = set() # 创建一个集合，用于存储所有不同的质因数
for x in nums: # 遍历数组中的每一个元素
i = 2 # 从2开始试除
while i * i <= x: # 只需检查到x的平方根
if x % i == 0: # 如果i是x的因子
s.add(i) # 将i添加到集合中
while x % i == 0: # 去除x中所有的i因子
x //= i
i += 1 # 增加i，检查下一个可能的因子
if x > 1: # 如果x仍大于1，则它本身必须是质数
s.add(x) # 将x添加到集合中
return len(s) # 返回集合中元素的数量，即不同质因数的数目
算法中使用的试除法的时间复杂度大致为O(n * sqrt(m))，其中n是数组长度，m是数组中的最大值。对每个数进行试除直到其平方根可以有效找出其所有质因数，但当数字非常大时，sqrt(m)仍然可能是一个很大的数，这会导致每个数的处理时间变长，从而增加整体的运算时间。对于极大数值，这种算法可能面临性能瓶颈，尤其是在内存和处理时间上。
如果一个数x可以被分解成两个因数的乘积，即x = a * b，那么在a和b中至少有一个不会大于x的平方根。如果两者都大于x的平方根，那么a * b会大于x，这与假设矛盾。因此，检查到x的平方根就足以找到所有可能的质因数。如果x不能被任何小于或等于其平方根的数整除，则x本身是质数。
对于非常大的数字，尤其是接近整数上限的数字，试除法需要检查的因数数量会非常多，这会导致算法运行缓慢，并且增加运算的复杂度。在实际的编程实践中，很大的数值处理还可能导致整数溢出问题，尤其是在某些编程环境中。虽然Python可以处理任意大小的整数，但对于其他一些语言，如C++或Java，可能需要特殊的库来处理大整数，或者修改算法以减少对大数直接运算的需求。