leetcode数论(2521. 数组乘积中的不同质因数数目)

前言

经过前期的基础训练以及部分实战练习，粗略掌握了各种题型的解题思路。现阶段开始专项练习。

数论包含最大公约数(>=2个数)、最大公约数性质、最小公倍数、区间范围质因素计数(最下间隔)、质因素分解、判断质数、平方根、立方根、互质、同余等等。

描述

给你一个正整数数组 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 <= 104
• 2 <= nums[i] <= 1000

实现原理与步骤

1.分析题干积的分解质因素和单个数字的质因素分解后的结果一致。

2.定义Set数据结果去重重复的质因素

3.枚举数组数据并分解质因素

4.分解质因素函数

实现代码

class Solution {public int distinctPrimeFactors(int[] nums) {Set<Integer> set=new HashSet();for(int i=0;i<nums.length;i++){getPrime(nums[i],set);}return set.size();}public void getPrime(int n,Set<Integer> set){while(n%2==0){set.add(2);n=n/2;}for(int i=3;i*i<=n;i+=2){while(n%i==0){set.add(i);n=n/i;}}if(n>2){set.add(n);}}
}

1.QA: