Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums.
Note that:
1 is called prime if it is divisible by only 1 and itself.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 <= 1042 <= nums[i] <= 1000Problem Overview: You are given an integer array nums. Multiply all numbers conceptually and return how many distinct prime factors appear in that product. Instead of computing the full product (which quickly overflows), factorize each number and track unique primes.
Approach 1: Prime Factorization with Trial Division (O(n * sqrt(m)) time, O(k) space)
Iterate through every value in nums and factorize it using trial division. For each number, repeatedly divide by 2, then test odd divisors up to sqrt(num). Every time you find a prime factor, insert it into a hash set to ensure uniqueness. If the remaining value after division is greater than 1, it is also a prime factor and should be added to the set. The final answer is the size of the set. This approach is simple and works well when numbers are small, but repeated sqrt factorization becomes expensive for large inputs.
Approach 2: Prime Factorization with Sieve (O(M log log M + total factors) time, O(M) space)
Precompute the smallest prime factor (SPF) for every number up to the maximum value in nums using a sieve. This preprocessing step is similar to the Sieve of Eratosthenes but stores the smallest prime divisor for each number. Once the SPF array is built, factorizing any number becomes fast: repeatedly divide by spf[x] and insert each prime into a hash set. Since factorization reduces the number quickly, the total work across the array stays small. This approach is ideal when the input contains many numbers or when the maximum value is moderately large.
Both solutions rely on tracking unique primes with a set (a common pattern when working with Hash Table problems). The main difference is how quickly each number is factorized. Trial division performs direct divisor checks, while the sieve converts factorization into repeated array lookups.
Conceptually, the task belongs to Number Theory combined with simple iteration over an Array. The key insight: the distinct primes in the product are simply the union of prime factors from every element.
Recommended for interviews: Trial division is often sufficient and easy to explain during interviews. It demonstrates understanding of prime factorization and set-based deduplication. The sieve-based solution shows stronger algorithmic depth and is preferable when constraints push trial division toward time limits.
This approach utilizes the Sieve of Eratosthenes to precompute prime numbers up to 1000 (the maximum possible element in the array). For each element in the array nums, determine its prime factors using the precomputed prime list and track them using a set to ensure each factor is counted only once.
The Python solution precomputes all prime numbers up to 1000 using the Sieve of Eratosthenes. For each integer in the input nums, it determines its distinct prime factors and adds them to a set. Finally, it returns the size of the set as the number of distinct prime factors.
Time Complexity: O(n log log max) where max is the largest number in nums (1000 in this case), due to the sieve. Space Complexity: O(n) where n is the number of distinct primes.
This approach uses trial division for prime factorization. For each element in the array, check divisibility starting from the smallest prime and record distinct primes in a set. This avoids the prerequisite computation of a list of primes.
The JavaScript solution uses trial division for discovering the prime factors of each array element and stores them in a set to ensure uniqueness.
JavaScript
C
Time Complexity: O(n sqrt(max)) assuming trial division up to the square root of each number. Space Complexity: O(n) for the distinct primes.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prime Factorization with Sieve | Time Complexity: O(n log log max) where max is the largest number in |
| Prime Factorization with Trial Division | Time Complexity: O(n sqrt(max)) assuming trial division up to the square root of each number. Space Complexity: O(n) for the distinct primes. |
| Hash Table + Prime Factorization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prime Factorization with Trial Division | O(n * sqrt(m)) | O(k) | Best for small numbers or quick interview implementation |
| Prime Factorization with Sieve (Smallest Prime Factor) | O(M log log M + total factors) | O(M) | Efficient when many numbers need factorization or max value is known |
2521. Distinct Prime Factors of Product of Array Hindi • ThinkCode • 1,316 views views
Watch 9 more video solutions →Practice Distinct Prime Factors of Product of Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor