# 2521. Distinct Prime Factors of Product of Array
###### tags: `Leetcode` `Medium` `Prime Factors` `Math`
Link: https://leetcode.com/problems/distinct-prime-factors-of-product-of-array/description/
## 思路
参考[这里](https://leetcode.com/problems/distinct-prime-factors-of-product-of-array/solutions/2977564/java-c-python-fully-explained/)
我们先要找到每个数字的prime factor 然后用set去重
找到一个数的prime factor的方法是 首先一直除以2 直到变成一个奇数
然后把从3到```sqrt(num)```的每一个奇数都试一遍 如果能整除 说明当下数字就是一个prime factor，一直除以当下数到除不尽为止
要知道一个数字不可能有两个大于sqrt(num)的prime factor
如果最后剩下的数字不等于1 就说明当下数字也是一个prime factor 并且是一个大于sqrt(num)的prime factor
## Code

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        prime_factors = set()
        
        def getPrimeFactors(num: int) -> set:
            prime_factors = set()

            while num % 2 == 0:
                prime_factors.add(2)
                num /= 2
            
            for i in range(3, int(math.sqrt(num))+1, 2):
                while num%i==0:
                    num/=i
                    prime_factors.add(i)
            if num!=1: prime_factors.add(num)
            return prime_factors
    
        for num in nums:
            current_factors = getPrimeFactors(num)
            prime_factors.update(current_factors)
        return len(prime_factors)