2521. Distinct Prime Factors of Product of Array

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.

• 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

Solution (Java)

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        int count=0;
        int[] a = new int[1001];
        //mark prime factors of all elements of nums using hashtable(a)
        for(int x:nums){
            primeFactors(x,a);
        }

        //counting all distinct prime factors
        for(int x:a){
            if(x==1)
                count++;
        }
        return count;
    }

    private void primeFactors(int x,int[] a)
    {
        int root = (int)Math.sqrt(x);
        for (int i=2; i<=root; i++) {
            while (x%i == 0) {
                x/=i;
                a[i]=1;
            }
        }

        if(x>=2)
            a[x]=1;
    }

}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).