侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学】数组乘积中的不同质因数数目

GabrielxD
2023-01-02 / 0 评论 / 0 点赞 / 11 阅读 / 386 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


给你一个正整数数组 nums ,对 nums 所有元素求积之后,找出并返回乘积中 不同质因数 的数目。

注意:

  • 质数 是指大于 1 且仅能被 1 及自身整除的数字。
  • 如果 val2 / val1 是一个整数,则整数 val1 是另一个整数 val2 的一个因数。

示例 1:

输入:nums = [2,4,3,7,10,6]
输出:4
解释:
nums 中所有元素的乘积是:2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7 。
共有 4 个不同的质因数,所以返回 4 。

示例 2:

输入:nums = [2,4,8,16]
输出:1
解释:
nums 中所有元素的乘积是:2 * 4 * 8 * 16 = 1024 = 210 。
共有 1 个不同的质因数,所以返回 1 。

提示:

  • 1 <= nums.length <= 10^4
  • 2 <= nums[i] <= 1000

解题

方法一:数学 分解质因数

思路

求乘积的不同质因数数量等于求所有乘数的质因数并去重得到的数量,具体来说:对所有数进行分解质因数并把质因数放入集合去重,集合大小便是不同质因数数量。

代码

class Solution {
    Set<Integer> pfs = new HashSet<>();

    public void pf(int n) {
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                pfs.add(i);
            }
        }
        if (n > 1) pfs.add(n);
    }

    public int distinctPrimeFactors(int[] nums) {
        for (int x : nums) pf(x);
        return pfs.size();
    }
}
0

评论区