Distinct prime factors of product of array

Array Hash Table Math Number Theory

54.2% acceptance

Feb 25, 2026

542

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distinct_prime_factors(nums: Vec<i32>) -> i32 {
    use std::collections::HashSet;
    let mut primes: HashSet<i32> = HashSet::new();
    for mut n in nums {
      let mut d = 2;
      while d * d <= n {
        while n % d == 0 {
          primes.insert(d);
          n /= d;
        }
        d += 1;
      }
      if n > 1 {
        primes.insert(n);
      }
    }
    primes.len() as i32
  }
}