蓝桥杯算法训练素因子去重（java）-白红宇的个人博客

蓝桥杯算法训练素因子去重（java）

发布日期：2021-05-09 04:15:21 浏览次数：17 分类：博客文章

本文共 836 字，大约阅读时间需要 2 分钟。

问题描述

　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1

输入格式

　　一个整数，表示n

输出格式

　　输出一行，包含一个整数p。

样例输入

1000

样例输出

数据规模和约定

　　n<=10^12

样例解释：n=1000=2^3*5*3，p=2*5=10

思路分析

i从2到n遍历一遍，

1. 判断i是否是n的因子并且是素数

2. 如果是素因子，则利用while循环，一直除以i来去重，素因子去重后，将素因子添加到集合中，i++,重复第1步

3. 如果不是素因子，i++，重复第1步

4. 循环结束后，将集合里的所有素因子相乘，即得到p

java 代码如下：

import java.util.ArrayList;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Long n = new Scanner(System.in).nextLong();        ArrayList
     
       list = new ArrayList
      
       ();        //从2到n找素因子        for (long i = 2; i <= n; i++) {            //i是素因子            if(n%i==0 && juge(i)){                //素因子去重                while(n%i==0){                    n/=i;                }                                //将素因子添加到集合                list.add(i);                if(n

上一篇：八大排序算法——选择排序（动图演示思路分析实例代码Java 复杂度分析）

下一篇：蓝桥杯每周一练第一周（3n+1问题）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章