首页 > 其他分享 >leetcode数论(2521. 数组乘积中的不同质因数数目)

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

时间:2024-08-04 09:52:34浏览次数:14  
标签:set 2521 乘积 nums int 质因素 质因数 leetcode

前言

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

数论包含最大公约数(>=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:

标签:set,2521,乘积,nums,int,质因素,质因数,leetcode
From: https://blog.csdn.net/acuteeagle01/article/details/140902001

相关文章

  • Leetcode 第 135 场双周赛题解
    Leetcode第135场双周赛题解Leetcode第135场双周赛题解题目1:3222.求出硬币游戏的赢家思路代码复杂度分析题目2:3223.操作后字符串的最短长度思路代码复杂度分析题目3:3224.使差值相等的最少数组改动次数思路代码复杂度分析题目4:思路代码复杂度分析Leetcode......
  • leetcode 021:删除链表的倒数第 N 个结点
    LCR021.删除链表的倒数第N个结点给定一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]示例3:输入:head=[1,2],n=1输出:[1]structListNode*removeNthF......
  • LeetCode | 160 Intersection of two linkedlists
    https://github.com/dolphinmind/datastructure/tree/datastructure-linkedlist分析判断两个链表是否相交,转换成了双指针相遇的问题。还是那句话,双指针的本质是遍历,走的路其实一样/***解决两个链接不相交而陷入无限循环的情况*初......
  • 【leetcode详解】正方形中的最多点数【中等】(C++思路精析)
    思路精析:自定义结构体解读:一个点是否在题给正方形中,只取决于其横纵坐标的最大值,记为dis沟通二位数组points和字符串s的桥梁,就是这个点的序号,记为idx由此自定义结构体,储存dis和idx//其中booloperator部分的功能:重载小于操作符“<”,使sort(vc.begin(),vc.end());按dis......
  • 代码随想录算法训练营Day18 | Leetcode 530 二叉搜索树的最小绝对差 Leetcode 236 二
    前言今天有一道题目没写,二叉搜索树中的众数,有点太难理解了,先放一放。Leetcode530二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)代码随想录题解:代码随想录(programmercarl.com)思路:二叉搜索树的性质是中序遍历为升序的,所以我们想找最小绝......
  • LeetCode面试150——238除自身以外数组的乘积
    题目难度:中等默认优化目标:最小化平均时间复杂度。Python默认为Python3。目录1题目描述2题目解析3算法原理及代码实现3.1左右乘积列表参考文献1题目描述给你一个整数数组nums,返回数组answer,其中answer[i]等于nums中除nums[i]之外其余各元素的乘积......
  • leetcode数论(2523. 范围内最接近的两个质数)
     前言经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。现阶段开始专项练习。描述给你两个正整数 left 和 right ,请你找到两个整数 num1 和 num2 ,它们满足:left<=nums1<nums2<=right  。nums1 和 nums2 都是 质数 。nums2-nums1......
  • LeetCode | 单链表操作
    LeetCode203移除链表元素LeetCode707设计链表LeetCode206反转链表主类ListNodepackagecom.github.dolphinmind.linkedlist.uitls;/***@authordolphinmind*@ClassNameListNode*@description*@date2024/8/3*///链表组成元素:节点publicclass......
  • LeetCode 1041. Robot Bounded In Circle
    原题链接在这里:https://leetcode.com/problems/robot-bounded-in-circle/description/题目:Onaninfiniteplane,arobotinitiallystandsat (0,0) andfacesnorth.Notethat:The northdirection isthepositivedirectionofthey-axis.The southdirection ......
  • LeetCode 1017. Convert to Base -2
    原题链接在这里:https://leetcode.com/problems/convert-to-base-2/description/题目:Givenaninteger n,return abinarystringrepresentingitsrepresentationinbase -2.Note thatthereturnedstringshouldnothaveleadingzerosunlessthestringis "0".......