前言
经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。现阶段开始专项练习。
数论包含最大公约数(>=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);
}
}
}