Problem Description

You are given an array of positive integers nums. Your task is to find the number of distinct prime factors that appear in the product of all elements in the array.

A prime number is a number greater than 1 that can only be divided evenly by 1 and itself. For example, 2, 3, 5, 7, 11 are prime numbers.

A number val1 is a factor of another number val2 if val2 divided by val1 gives an integer result (no remainder).

The key insight is that you need to find all unique prime numbers that divide at least one element in the array. When you multiply all elements together to get the product, these prime factors will be part of the prime factorization of that product.

For example, if nums = [2, 4, 3, 7, 10, 6]:

• The product is 2 × 4 × 3 × 7 × 10 × 6 = 10080
• Breaking down each number into prime factors:
  • 2 = 2
  • 4 = 2²
  • 3 = 3
  • 7 = 7
  • 10 = 2 × 5
  • 6 = 2 × 3
• The distinct prime factors are: 2, 3, 5, 7
• So the answer is 4

The solution uses prime factorization for each number in the array and collects all unique prime factors using a set data structure. For each number, it finds all prime factors by trial division starting from 2, and adds them to the set. The final answer is the size of this set.

Intuition

The key observation is that when we multiply all numbers in the array together, the prime factorization of the product will contain all prime factors from individual numbers. However, we don't actually need to compute this potentially huge product.

Think about it this way: if a prime number p divides any number in the array, then p will also divide the product of all numbers. For example, if 2 divides 10 in the array, then 2 will definitely divide the final product regardless of what other numbers are present.

This leads us to a simpler approach: instead of calculating the product first (which could cause overflow), we can find prime factors of each number individually and collect them. Since we only care about distinct prime factors, not their frequencies, we can use a set to automatically handle duplicates.

The process becomes:

1. For each number in the array, find all its prime factors
2. Add these prime factors to a set (which keeps only unique values)
3. The size of the set gives us the count of distinct prime factors

For prime factorization itself, we use trial division: we try dividing by potential factors starting from 2. When we find a factor i, we keep dividing by i until it's no longer a factor (this handles prime powers like 2³ in 8). We only need to check factors up to √n because if n has a factor larger than √n, it can have at most one such factor, and that factor would be n itself after removing all smaller prime factors.

This approach is efficient because we avoid computing large products and instead work with each number independently, collecting unique prime factors as we go.

Learn more about Math patterns.

Solution Approach

The solution uses a hash table (set) combined with prime factorization to find all distinct prime factors across the array elements.

Data Structure Used:

• A set to store unique prime factors found across all numbers

Algorithm Steps:

1. Initialize an empty set s to store distinct prime factors.

2. Iterate through each number n in the input array nums.

3. For each number, perform prime factorization:

   • Start with the smallest prime candidate i = 2
   • While i <= n // i (equivalent to i <= √n):
     • Check if i is a factor of n by testing n % i == 0
     • If i is a factor:
       • Add i to the set (it's a prime factor)
       • Completely remove this prime factor by repeatedly dividing: while n % i == 0: n //= i
     • Increment i to check the next potential factor

4. Handle remaining prime factor:

   • After the loop, if n > 1, then n itself is a prime factor
   • This happens when n has a prime factor greater than √n
   • Add this remaining n to the set

5. Return the result: The size of the set len(s) gives the count of distinct prime factors.

Why this works:

• The condition i <= n // i ensures we only check divisors up to √n, which is sufficient because any composite number must have at least one prime factor ≤ √n
• The inner while loop while n % i == 0: n //= i removes all occurrences of prime i from n, effectively extracting the prime and reducing n
• By dividing out each prime factor completely, we ensure that each i that divides n is actually prime (not composite)
• Using a set automatically handles duplicates - if multiple numbers share the same prime factor, it's only counted once

Time Complexity: O(m × √k) where m is the length of the array and k is the maximum value in the array.

Space Complexity: O(p) where p is the number of distinct prime factors found.

Example Walkthrough

Let's walk through the solution with nums = [12, 15, 10].

Step 1: Initialize empty set

• s = {}

Step 2: Process first number (12)

• n = 12, start with i = 2
• Check if 2 divides 12: Yes (12 % 2 == 0)
  • Add 2 to set: s = {2}
  • Remove all 2's: 12 ÷ 2 = 6, then 6 ÷ 2 = 3
  • Now n = 3
• Increment to i = 3
• Check condition 3 <= 3 // 3 (3 <= 1): False, exit loop
• Check remaining: n = 3 > 1, so add 3 to set
• After processing 12: s = {2, 3}

Step 3: Process second number (15)

• n = 15, start with i = 2
• Check if 2 divides 15: No (15 % 2 ≠ 0)
• Increment to i = 3
• Check if 3 divides 15: Yes (15 % 3 == 0)
  • Add 3 to set: s = {2, 3} (3 already exists, no change)
  • Remove all 3's: 15 ÷ 3 = 5
  • Now n = 5
• Increment to i = 4
• Check condition 4 <= 5 // 4 (4 <= 1): False, exit loop
• Check remaining: n = 5 > 1, so add 5 to set
• After processing 15: s = {2, 3, 5}

Step 4: Process third number (10)

• n = 10, start with i = 2
• Check if 2 divides 10: Yes (10 % 2 == 0)
  • Add 2 to set: s = {2, 3, 5} (2 already exists, no change)
  • Remove all 2's: 10 ÷ 2 = 5
  • Now n = 5
• Increment to i = 3
• Check condition 3 <= 5 // 3 (3 <= 1): False, exit loop
• Check remaining: n = 5 > 1, so add 5 to set
• After processing 10: s = {2, 3, 5} (5 already exists, no change)

Step 5: Return result

• Final set: s = {2, 3, 5}
• Return len(s) = 3

The answer is 3 distinct prime factors. We can verify: the product 12 × 15 × 10 = 1800 = 2³ × 3² × 5², which indeed has exactly three distinct prime factors: 2, 3, and 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × √m)

The algorithm iterates through each of the n numbers in the array. For each number, it performs prime factorization using trial division. The key optimization is the condition i <= n // i (equivalent to i² <= n), which means we only check divisors up to √n. In the worst case, when factorizing the maximum value m in the array, we check up to √m potential divisors. Therefore, the overall time complexity is O(n × √m).

Space Complexity: O(m / log m)

The space is primarily used by the set s to store distinct prime factors. According to the Prime Number Theorem, the number of primes less than or equal to m is approximately m / ln(m). Since we're storing only the distinct prime factors from all numbers in the array, and these prime factors cannot exceed m, the maximum number of distinct primes we can store is bounded by O(m / log m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Large Prime Factors Correctly

A critical pitfall occurs when forgetting to check if num > 1 after the factorization loop. This remaining value represents a prime factor larger than √num.

Incorrect Implementation:

for num in nums:
    divisor = 2
    while divisor * divisor <= num:
        if num % divisor == 0:
            prime_factors.add(divisor)
            while num % divisor == 0:
                num //= divisor
        divisor += 1
    # Missing: if num > 1: prime_factors.add(num)

Problem: This misses prime factors greater than √num. For example, with num = 14:

• After dividing by 2, we get 7
• Since 3² = 9 > 7, the loop ends
• We never add 7 to our prime factors set

Solution: Always check and add the remaining value if it's greater than 1.

2. Inefficient Prime Checking with divisor++

Using divisor += 1 checks all numbers, including even numbers after 2, which wastes computation.

Inefficient Approach:

divisor = 2
while divisor * divisor <= num:
    # ... factorization logic ...
    divisor += 1  # Checks 2, 3, 4, 5, 6, 7, 8...

Optimized Solution:

divisor = 2
while divisor * divisor <= num:
    if num % divisor == 0:
        prime_factors.add(divisor)
        while num % divisor == 0:
            num //= divisor
  
    # Skip even numbers after 2
    if divisor == 2:
        divisor = 3
    else:
        divisor += 2  # Only check odd numbers: 3, 5, 7, 9...

3. Not Removing All Occurrences of a Prime Factor

Failing to completely divide out a prime factor can lead to treating composite numbers as primes.

Incorrect Implementation:

if num % divisor == 0:
    prime_factors.add(divisor)
    num //= divisor  # Only divides once!
    divisor += 1

Problem: For num = 12 (which is 2² × 3):

• After dividing by 2 once, we get 6
• We then check if 3 divides 6, but 6 still contains factor 2
• This could lead to incorrect identification of prime factors

Solution: Use a while loop to completely remove each prime factor:

while num % divisor == 0:
    num //= divisor

4. Integer Overflow in Condition Check

Using divisor * divisor <= num can cause integer overflow for very large numbers in some languages.

Safer Alternative:

while divisor <= num // divisor:  # Mathematically equivalent but avoids overflow
    # ... factorization logic ...

This prevents potential overflow issues when divisor is large, though Python handles big integers naturally.