Java 蓝桥杯算法训练 ALGO_190_素因子去重

水深无声 2022-12-14 12:25 132阅读 0赞

## Java 蓝桥杯 算法训练 ALGO\_190\_素因子去重 ##

## 问题描述 ##

给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1  
输入格式  
　　一个整数，表示n  
输出格式  
　　输出一行，包含一个整数p。  
样例输入  
1000  
样例输出  
10  
数据规模和约定  
　　n<=10^12  
　　样例解释：n=1000=2^3*5*3，p=2\*5=10

/*
     *@author  MingxuDeng
     *@version 20202020年10月13日
    
    问题描述
    	　　		给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1
    	输入格式
    	　　		一个整数，表示n
    	输出格式
    	　　		输出一行，包含一个整数p。
    	样例输入
    			1000
    	样例输出
    			10
    	
    	数据规模和约定
    	　　		n<=10^12
    	样例解释：n=1000=2^3*5*3，p=2*5=10
    */
    package ALGO;
    
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Scanner;
    import java.util.Set;
    
    public class ALGO_190_素因子去重 {
        
    	// 多态： new 一个 HashSet 类型的 Set 对象，泛型为 long。
    	static Set<Long> set = new HashSet<Long>();// Set 的特点：在 Set 中，不能存放重复的数值。
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		Scanner s = new Scanner(System.in);
    		//数据规模和约定： n<=10^12
    		long n = s.nextLong();long d=n,p = 1l;
    		for (int i = 2; i < n/2; i++) {
        //从2开始遍历，直到 n/2 为止，在此区间寻找可能的因子
    			while(d%i==0) {
        //选取满足条件的因子，并把它存到 set 集合中去
    				// boolean add(E e)：如果 set 中尚未存在指定的元素，则添加此元素（可选操作）。
    				set.add((long)i);
    				d/=i;//动态更新 d 的值，保证 for 循环接下来的遍历区间的更新。(此时的 d != 之前的 d)
    			}
    			if(d<i) break;//当 d 小于 i 时 遍历结束
    		}
    		set.add(d);//最后一个最小的因子不能忘记
    		/*
    		 	由于 Set 集合没有自带的取值的方法，此时就需要迭代器来实现对集合中的数据进行读取的功能，
    		 	所以需要 new 一个迭代器的类对象，并使用其对象中的相关方法以达到获取集合中值的目的，如下：
    		 */
    		Iterator<Long> iterator = set.iterator();// new 一个 Iterator 来接受set中的数据。
    		//iterator.hasNext()方法：返回 Boolean 值，从第0-1个位置开始判断：下一个位置是否有数据，有返回 true，否则返回 false。
    		while(iterator.hasNext()){
        //当下一个位置还有值的时候， iterator.next() 方法取出下一个位置的值。
    			p *= iterator.next();//p 乘等于 下一个位置的值
    		}
    		System.out.println(p);//打印输出 p 
    	}
    }

[友情链接][Link 1]

[Link 1]: https://blog.csdn.net/qq_39445165/article/details/88314924