Question

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

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)

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();
  }
}

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();
  }
};

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)
}