README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/2500-2599/2521.Distinct%20Prime%20Factors%20of%20Product%20of%20Array/README_EN.md	1413	Weekly Contest 326 Q2	Array Hash Table Math Number Theory

2521. Distinct Prime Factors of Product of Array

中文文档

Description

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.
• An integer val1 is a factor of another integer val2 if val2 / val1 is an integer.

 

Example 1:

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.
There are 4 distinct prime factors so we return 4.

Example 2:

Input: nums = [2,4,8,16]
Output: 1
Explanation:
The product of all the elements in nums is: 2 * 4 * 8 * 16 = 1024 = 210.
There is 1 distinct prime factor so we return 1.

 

Constraints:

• 1 <= nums.length <= 104
• 2 <= nums[i] <= 1000

Solutions

Solution 1: Hash Table + Prime Factorization

For each element in the array, first perform prime factorization on it, and then add the decomposed prime factors to the hash table. Finally, return the size of the hash table.

The time complexity is $O(n \times \sqrt{m})$, and the space complexity is $O(\frac{m}{\log m})$. Where $n$ and $m$ are the length of the array and the maximum value in the array, respectively.

Python3

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)

Java

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int n : nums) {
            for (int i = 2; i <= n / i; ++i) {
                if (n % i == 0) {
                    s.add(i);
                    while (n % i == 0) {
                        n /= i;
                    }
                }
            }
            if (n > 1) {
                s.add(n);
            }
        }
        return s.size();
    }
}

C++

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_set<int> s;
        for (int& n : nums) {
            for (int i = 2; i <= n / i; ++i) {
                if (n % i == 0) {
                    s.insert(i);
                    while (n % i == 0) {
                        n /= i;
                    }
                }
            }
            if (n > 1) {
                s.insert(n);
            }
        }
        return s.size();
    }
};

Go

func distinctPrimeFactors(nums []int) int {
	s := map[int]bool{}
	for _, n := range nums {
		for i := 2; i <= n/i; i++ {
			if n%i == 0 {
				s[i] = true
				for n%i == 0 {
					n /= i
				}
			}
		}
		if n > 1 {
			s[n] = true
		}
	}
	return len(s)
}

TypeScript

function distinctPrimeFactors(nums: number[]): number {
    const s: Set<number> = new Set();
    for (let n of nums) {
        let i = 2;
        while (i <= n / i) {
            if (n % i === 0) {
                s.add(i);
                while (n % i === 0) {
                    n = Math.floor(n / i);
                }
            }
            ++i;
        }
        if (n > 1) {
            s.add(n);
        }
    }
    return s.size;
}