Distinct Prime Factors of Product of Array — LeetCode 2521 Python Solution

The problem

Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums. Note that: A number greater than 1 is called prime if it is divisible by only 1 and itself.

Example

Input

nums = [2,4,3,7,10,6]

Output

4

Explanation

The product of all the elements in nums is: 2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7.

Python solution

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)

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2521. Distinct Prime Factors of Product of Array is filed here because LeetCode tags it Math and Number Theory, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems