Problem

Given an array of positive integers nums, return the number ofdistinct 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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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 <= 10^4
  • 2 <= nums[i] <= 1000

Solution

Method 1 – Prime Factorization with Sieve

Intuition

The product of all numbers in the array can be very large, but we only care about the set of distinct prime factors among all elements. Since each number is at most 1000, we can precompute all primes up to 1000 and factorize each number in the array, collecting all unique primes.

Approach

  1. Use the Sieve of Eratosthenes to generate all primes up to 1000.
  2. For each number in nums, factorize it using the list of primes and add each found prime to a set.
  3. The answer is the size of the set of unique primes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        vector<int> primes;
        vector<bool> is_prime(1001, true);
        for (int i = 2; i <= 1000; ++i) {
            if (is_prime[i]) {
                primes.push_back(i);
                for (int j = i * 2; j <= 1000; j += i) is_prime[j] = false;
            }
        }
        unordered_set<int> st;
        for (int x : nums) {
            for (int p : primes) {
                if (p * p > x) break;
                if (x % p == 0) {
                    st.insert(p);
                    while (x % p == 0) x /= p;
                }
            }
            if (x > 1) st.insert(x);
        }
        return st.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func distinctPrimeFactors(nums []int) int {
    isPrime := make([]bool, 1001)
    for i := 2; i <= 1000; i++ {
        isPrime[i] = true
    }
    primes := []int{}
    for i := 2; i <= 1000; i++ {
        if isPrime[i] {
            primes = append(primes, i)
            for j := i * 2; j <= 1000; j += i {
                isPrime[j] = false
            }
        }
    }
    st := map[int]struct{}{}
    for _, x := range nums {
        for _, p := range primes {
            if p*p > x {
                break
            }
            if x%p == 0 {
                st[p] = struct{}{}
                for x%p == 0 {
                    x /= p
                }
            }
        }
        if x > 1 {
            st[x] = struct{}{}
        }
    }
    return len(st)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        boolean[] isPrime = new boolean[1001];
        Arrays.fill(isPrime, true);
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= 1000; ++i) {
            if (isPrime[i]) {
                primes.add(i);
                for (int j = i * 2; j <= 1000; j += i) isPrime[j] = false;
            }
        }
        Set<Integer> st = new HashSet<>();
        for (int x : nums) {
            for (int p : primes) {
                if (p * p > x) break;
                if (x % p == 0) {
                    st.add(p);
                    while (x % p == 0) x /= p;
                }
            }
            if (x > 1) st.add(x);
        }
        return st.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun distinctPrimeFactors(nums: IntArray): Int {
        val isPrime = BooleanArray(1001) { true }
        val primes = mutableListOf<Int>()
        for (i in 2..1000) {
            if (isPrime[i]) {
                primes.add(i)
                for (j in i * 2..1000 step i) isPrime[j] = false
            }
        }
        val st = mutableSetOf<Int>()
        for (x0 in nums) {
            var x = x0
            for (p in primes) {
                if (p * p > x) break
                if (x % p == 0) {
                    st.add(p)
                    while (x % p == 0) x /= p
                }
            }
            if (x > 1) st.add(x)
        }
        return st.size
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def distinctPrimeFactors(self, nums: list[int]) -> int:
        def sieve(n: int) -> list[int]:
            is_prime = [True] * (n + 1)
            primes = []
            for i in range(2, n + 1):
                if is_prime[i]:
                    primes.append(i)
                    for j in range(i * 2, n + 1, i):
                        is_prime[j] = False
            return primes
        primes = sieve(1000)
        st: set[int] = set()
        for x in nums:
            for p in primes:
                if p * p > x:
                    break
                if x % p == 0:
                    st.add(p)
                    while x % p == 0:
                        x //= p
            if x > 1:
                st.add(x)
        return len(st)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

impl Solution {
    pub fn distinct_prime_factors(nums: Vec<i32>) -> i32 {
        let mut is_prime = vec![true; 1001];
        let mut primes = vec![];
        for i in 2..=1000 {
            if is_prime[i] {
                primes.push(i as i32);
                let mut j = i * 2;
                while j <= 1000 {
                    is_prime[j] = false;
                    j += i;
                }
            }
        }
        let mut st = std::collections::HashSet::new();
        for mut x in nums {
            for &p in &primes {
                if p * p > x {
                    break;
                }
                if x % p == 0 {
                    st.insert(p);
                    while x % p == 0 {
                        x /= p;
                    }
                }
            }
            if x > 1 {
                st.insert(x);
            }
        }
        st.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    distinctPrimeFactors(nums: number[]): number {
        const isPrime = Array(1001).fill(true);
        const primes: number[] = [];
        for (let i = 2; i <= 1000; ++i) {
            if (isPrime[i]) {
                primes.push(i);
                for (let j = i * 2; j <= 1000; j += i) isPrime[j] = false;
            }
        }
        const st = new Set<number>();
        for (let x of nums) {
            for (const p of primes) {
                if (p * p > x) break;
                if (x % p === 0) {
                    st.add(p);
                    while (x % p === 0) x /= p;
                }
            }
            if (x > 1) st.add(x);
        }
        return st.size;
    }
}

Complexity

  • ⏰ Time complexity: O(n * sqrt(m)), where n is the length of nums and m is the maximum value in nums (here, m=1000). Each number is factorized in O(sqrt(m)) time.
  • 🧺 Space complexity: O(m), for the sieve and the set of primes.