2521.数组乘积中的不同质因数数目

链接：2521.数组乘积中的不同质因数数目
难度：Medium
标签：数组、哈希表、数学、数论
简介：给给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。

题解 1 - rust

• 编辑时间：2023-01-01
• 执行用时：84ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：遍历。

use std::collections::HashSet;
impl Solution {
    pub fn distinct_prime_factors(nums: Vec<i32>) -> i32 {
        let mut set = HashSet::<i32>::new();
        for num in nums {
            Solution::load(&mut set, num);
        }
        set.len() as i32
    }
    fn load(set: &mut HashSet<i32>, num: i32) {
        let mut num = num;
        let mut i = 2;
        while i <= num {
            if i > num {
                break;
            }
            if num % i == 0 {
                set.insert(i);
            }
            while num % i == 0 {
                num /= i;
            }
            i += 1;
        }
    }
}

题解 2 - cpp

• 编辑时间：2023-01-01
• 执行用时：80ms
• 内存消耗：18.3MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int distinctPrimeFactors(vector<int>& nums) {
        unordered_set<int> s;
        for (auto &num : nums) {
            load(s, num);
        }
        return s.size();
    }
    void load(unordered_set<int> &s, int num) {
        for (int i = 2; i <= num; i++) {
            if (num % i == 0) {
                s.insert(i);
                while (num % i == 0) num /= i;
            }
        }
    }
};