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 <= 1042 <= 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);}}
}