# Distinct Prime Factors of Product of Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/distinct-prime-factors-of-product-of-array)
Canonical: https://scaleengineer.com/dsa/problems/distinct-prime-factors-of-product-of-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Hash Table
---
## 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`

# Approaches
## Brute-Force Prime Factorization
This approach iterates through each number in the input array `nums`. For each number, it finds all its prime factors using trial division. A `HashSet` is used to store the distinct prime factors found across all numbers. The final answer is the size of this set.
**Time:** O(N * sqrt(M)), where N is the number of elements in `nums` and M is the maximum value of an element in `nums`. For each of the N numbers, we perform trial division up to `sqrt(M)`. · **Space:** O(P_M), where P_M is the number of prime numbers less than or equal to M (the maximum value in `nums`). This space is used by the `HashSet`. Since M <= 1000, the number of primes is a small constant (168), so the space can be considered O(1).
**Pros:** Simple to understand and implement.; Does not require any pre-computation.; Space efficient as it only stores the final prime factors.
**Cons:** Less efficient than approaches using pre-computation, as it repeatedly calculates factors for numbers.; The factorization step `O(sqrt(M))` is slower than the `O(log M)` factorization possible with sieves.
### Explanation
The core idea is that the set of prime factors of the product of several numbers is the union of the sets of prime factors of each individual number. This avoids calculating the potentially huge product which would cause an overflow.

We initialize a `HashSet` to keep track of the unique prime factors. We then loop through each `num` in the `nums` array. For each `num`, we perform prime factorization by trial division. We start with a divisor `d = 2` and check for divisibility. If `d` divides `num`, we add `d` to our `HashSet` and then divide `num` by `d` repeatedly until it's no longer divisible. This ensures we handle powers of a prime factor (like `8 = 2*2*2`) correctly. We then increment `d` and repeat the process. We only need to check divisors up to the square root of the current `num`. If, after the loop, the remaining value of `num` is greater than 1, it must be a prime factor itself (e.g., when factorizing 14, after dividing by 2, we are left with 7). We add this remaining number to the set. Finally, the number of distinct prime factors is simply the size of the `HashSet`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> primeFactors = new HashSet<>();
        for (int num : nums) {
            findPrimeFactors(num, primeFactors);
        }
        return primeFactors.size();
    }

    private void findPrimeFactors(int n, Set<Integer> factors) {
        // Trial division to find prime factors
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        // If n is a prime number greater than 1 after the loop
        if (n > 1) {
            factors.add(n);
        }
    }
}
```
### Algorithm
- Initialize an empty `HashSet<Integer>` named `distinctPrimes`.
- Iterate through each integer `num` in the input array `nums`.
- For each `num`, find its prime factors:
  - Iterate with a divisor `d` from 2 up to `sqrt(num)`.
  - If `d` divides `num`:
    - Add `d` to the `distinctPrimes` set.
    - Continuously divide `num` by `d` until it is no longer divisible.
  - After the loop, if `num` is still greater than 1, it is a prime factor itself. Add it to `distinctPrimes`.
- Return the final size of the `distinctPrimes` set.

## Optimized Factorization with Sieve
This approach improves upon the brute-force method by pre-computing the smallest prime factor (SPF) for all numbers up to the maximum possible value in the input array (1000). This pre-computation is done using a Sieve. With the SPF array, finding the prime factors of any number becomes much faster, changing the complexity from `O(sqrt(M))` to `O(log M)` per number.
**Time:** O(M log log M + N * log M). The sieve pre-computation takes `O(M log log M)`. Then, for each of the N numbers, factorization takes `O(log M)` time because in each step we divide the number by at least its smallest prime factor (which is >= 2). · **Space:** O(M), where M is the maximum value in `nums`. We need an array of size `M+1` for the sieve (`spf` array). The `HashSet` also uses space, but it's bounded by the number of primes up to M, which is less than M.
**Pros:** Very efficient for the given constraints, as the factorization step is much faster (`O(log M)`).; The pre-computation is done only once, making it highly effective if the function is called multiple times with numbers within the same range.
**Cons:** Requires extra space `O(M)` for the sieve array.; More complex to implement due to the pre-computation step.
### Explanation
The main bottleneck in the previous approach is the `O(sqrt(M))` factorization step for each number. We can optimize this by pre-calculating information. Since all numbers are bounded by 1000, we can use a Sieve of Eratosthenes variant to build a "Smallest Prime Factor" (SPF) array.

**Step 1: Pre-computation (Sieve)**
We create an integer array `spf` of size 1001. We initialize `spf[i] = i` for all `i`. Then, we iterate from `p = 2` up to `sqrt(1000)`. If `spf[p]` is still `p`, it means `p` is a prime number. For each prime `p`, we iterate through its multiples and update their smallest prime factor to `p`.

**Step 2: Factorization**
With the `spf` array ready, we initialize an empty `HashSet` to store distinct prime factors. We iterate through each `num` in the `nums` array. To factorize `num`, we repeatedly find its smallest prime factor `p = spf[num]`, add `p` to our set, and then divide `num` by `p` until it's no longer divisible. We continue this process until `num` becomes 1.

**Step 3: Result**
The size of the `HashSet` gives the final count of distinct prime factors.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    private static final int MAX_VAL = 1000;
    private static final int[] spf = new int[MAX_VAL + 1];

    // Static block for one-time pre-computation
    static {
        for (int i = 2; i <= MAX_VAL; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i <= MAX_VAL; i++) {
            if (spf[i] == i) { // i is a prime
                for (int j = i * i; j <= MAX_VAL; j += i) {
                    if (spf[j] == j) { // if spf[j] is not set yet
                        spf[j] = i;
                    }
                }
            }
        }
    }

    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> distinctPrimes = new HashSet<>();
        for (int num : nums) {
            int currentNum = num;
            while (currentNum > 1) {
                int p = spf[currentNum];
                distinctPrimes.add(p);
                while (currentNum % p == 0) {
                    currentNum /= p;
                }
            }
        }
        return distinctPrimes.size();
    }
}
```
### Algorithm
- **Pre-computation:**
  - Create an array `spf` (Smallest Prime Factor) of size `M+1`, where `M` is the maximum possible value of `nums[i]` (1000).
  - Use a Sieve-like algorithm to populate `spf`. Initialize `spf[i] = i`. Iterate from `p=2` to `sqrt(M)`. If `p` is prime (`spf[p] == p`), mark `p` as the smallest prime factor for all its multiples.
- **Main Logic:**
  - Initialize an empty `HashSet<Integer>` named `distinctPrimes`.
  - Iterate through each integer `num` in the input array `nums`.
  - While `num > 1`:
    - Find the smallest prime factor `p = spf[num]`.
    - Add `p` to the `distinctPrimes` set.
    - Divide `num` by `p` repeatedly until it's no longer divisible to remove all occurrences of this factor.
- Return the size of the `distinctPrimes` set.

# Solutions
### Java

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

### CPP

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

### Python

```python
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 )
```