文档章节

蓝桥杯 算法训练 素因子去重 (java)

o
 osc_a22drz29
发布于 2019/03/23 17:06
字数 374
阅读 14
收藏 0

精选30+云产品,助力企业轻松上云!>>>

问题描述
  给定一个正整数n,求一个正整数p,满足p仅包含n的所有素因子,且每个素因子的次数不大于1
 
输入格式
  一个整数,表示n
 
输出格式
  输出一行,包含一个整数p。
 
样例输入
1000
 
样例输出
10
 
数据规模和约定
  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<Long> list = new ArrayList<Long>();
        //从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<i)
                    break;
            }
        }
        
        long p = 1;
        //将所有素因子相乘,得出最后结果p
        for (int i = 0; i < list.size(); i++) {
            p*=(long)list.get(i);
        }
        System.out.println(p);
    }
    
    //判断因子是否是素数
    public static boolean juge(long m){
        int sqrt = (int) Math.sqrt(m);
        for (int i = 2; i <= sqrt; i++) {
            if(m%i==0)
                return false;
        }
        return true;
    }
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
蓝桥杯算法训练之题记

链接:http://lx.lanqiao.cn/index.page 来源:蓝桥杯 文章目录 算法训练 审美课(位运算) 算法训练 素因子去重(数论(素数)) 算法训练 P0505(高精度 * 单精度(模板),离线计算) 算法训练 最大最小...

osc_5dotef4h
2019/03/01
2
0
蓝桥杯Java真题解析

上个月参加蓝桥杯省赛拿了个省一,自从比赛完之后就一直没怎么写代码了,还有一个多月就要国赛了,从现在开始准备下国赛,但是我也不想学什么算法,而且我还在准备考研,所以就打算只做下历年...

osc_xbbkgf7t
2019/04/18
1
0
2-java-写代码技巧和交题注意点

用java交题要严格按照规定写代码: 比如蓝桥杯就是: 1.不能有包名; 2.Class的名字必须是 Main; 代码补全建议: 1.main函数的头可以建立class时候直接勾选,也可以: 只输入 main, 然后alt...

osc_3fp081wq
2018/11/23
4
0
【广州】被客户叼晕了的【Java程序员】,来此【求职】哈~

先来些简历信息,让各位HR或主管经理过过目。。。 有木有单位愿意收留俺这枚应届生,屌丝程序猿。。。 专业能力:掌握Java语言编程,熟练JSP、Servlet、JDBC下开发; 熟悉Struts、Hibernate...

__啊
2014/07/23
2.8K
23
【算法】蓝桥杯dfs深度优先搜索之凑算式总结

导航 本文 → 《【算法】蓝桥杯dfs深度优先搜索之凑算式总结》 相关文章 →《【算法】蓝桥杯dfs深度优先搜索之排列组合总结》 →《【算法】蓝桥杯dfs深度优先搜索之图连通总结》 前言 曾几何...

osc_kfnbvkb9
2019/03/21
10
0

没有更多内容

加载失败,请刷新页面

加载更多

Buffer的创建及使用源码分析——ByteBuffer为例

目录 Buffer概述 Buffer的创建 Buffer的使用 总结 参考资料 Buffer概述 注:全文以ByteBuffer类为例说明 在Java中提供了7种类型的Buffer,每一种类型的Buffer根据分配内存的方式不同又可以分为...

osc_zoa046qb
15分钟前
11
0
《 ZooKeeper : Wait-free coordination for Internet-scale systems 》论文研读

Zookeeper 研读 说明:本文为论文 《 ZooKeeper : Wait-free coordination for Internet-scale systems 》 的个人理解,难免有理解不到位之处,欢迎交流与指正 。 论文地址:Zookeeper Paper...

osc_4isxawz4
16分钟前
16
0
利用__new__实现单例模式

26 利用__new__实现单例模式 python当中有很多方法都可以实现单例模式, 但利用__new__无疑是最推荐的方式. 代码如下: class Demo:is_instance = Nonedef __new__(cls, *args, **kwargs...

_Change_
17分钟前
4
0
如何白嫖微软Azure12个月及避坑指南

Azure是微软提供的一个云服务平台。是全球除了AWS外最大的云服务提供商。Azure是微软除了windows之外另外一个王牌,微软错过了移动端,还好抓住了云服务。这里的Azure是Azure国际不是Azure中...

osc_dwuu5jqk
17分钟前
0
0
Mybatis源码初探——优雅精良的骨架

@ 目录 前言 精良的Mybatis骨架 宏观设计 基础支撑 日志 日志的加载 日志的使用 数据源 数据源的创建 池化技术原理 数据结构 获取连接 回收连接 缓存 缓存的实现 CacheKey 反射 总结 前言 My...

osc_r9wwwi0j
19分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部