aboutsummaryrefslogtreecommitdiff
path: root/distinct_prime_factors_arr.py
blob: c8c9a7a97bbae3b06d60fccb83587e968aacb93a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 2521. Distinct Prime Factors of Product of Array
from math import sqrt

"""
given an array of positive integers 'nums', return the number of distinct
prime factors in the product of the element of 'nums'. note that a number
greater than 1 is called prime if it is divisible by only 1 and itself. an
integer 'val1' is a factor of another integer 'val2' if 'val2 / val1' is an
integer
"""


class Solution(object):
    def distinctPrimeFactors(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        arr = []
        for i in range(len(nums)):
            root = int(sqrt(nums[i]))
            for num in range(2, root + 1):
                if nums[i] % num == 0:
                    arr.append(num)
                    while nums[i] % num == 0:
                        nums[i] = nums[i] // num
            if nums[i] >= 2:
                arr.append(nums[i])
        arr = set(arr)
        return len(arr)


if __name__ == "__main__":
    obj = Solution()
    print(obj.distinctPrimeFactors(nums=[2, 4, 3, 7, 10, 6]))
    print(obj.distinctPrimeFactors(nums=[2, 4, 8, 16]))