美文网首页
算法训练 素因子去重

算法训练 素因子去重

作者: 就这样吧嘞 | 来源:发表于2019-02-25 20:38 被阅读0次

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

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int a = sc.nextInt();
        int cc[]= new int [a+1];
        int i=0;
        while(panduan(a)!=true) {
            int m=chaifen(a);
            cc[i]=m;
            i++;
            a=a/m;
//          System.out.println(m);
        }
        cc[i]=a;
//      for(int j=0;j<=i;j++) {
//          System.out.println(cc[j]);
//      }
        
        int sz[]=new int [i+1];
        for(int p=0;p<i+1;p++) {
            sz[p]=cc[p];
        }
        int m=quchong(sz);
        System.out.println(m);
        
        
        
        
        

        
    }
    public static int quchong(int sz[]) {//去重算积
        int m=1;
        for(int i=0;i<sz.length;i++) {
            int jishu=0;
            for(int j=0;j<=i;j++) {
                if(jishu==i) {
//                  System.out.println(sz[i]);
                    m=m*sz[i];
                }
                if(sz[i]==sz[j]) {
                    break;
                }
                else {
                    jishu++;
                }
            }
        }
        return m;
    }
    
    
    
    public static int chaifen(int a) {//拆分
        int cf = 0 ;
        if(a<2) {
            cf = a;
        }
        else {
            for(int i =2;i<=a;i++) {
                if(a%i==0) {
                    cf=i;
                    break;
                }
            }
        }
        return cf;
    }
    
    
    public static boolean panduan(int x) {//判断是否是质数
        if(x<2) {
            return true;
        }
        else {
            for(int i=2;i<x;i++) {
                if(x%i==0) {
                    return false;
                }
            }
        }
        return true;
    }
}



内存超限

相关文章

  • 算法训练 素因子去重

    问题描述给定一个正整数n,求一个正整数p,满足p仅包含n的所有素因子,且每个素因子的次数不大于1输入格式一个整数,...

  • 胰岛素样生长因子一1的活性如何检测?

    胰岛素样生长因子一1(Insulin―like Growth Factor―l,IGF 1)是胰岛素样生长因子的重...

  • Day85 第 k 个数

    有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素...

  • R常用命令

    将因子转化成数字: 去重 画图

  • 第十章 数据推荐算法——基于潜在因子算法的推荐

    10.4 基于潜在因子算法的推荐 基于潜在因子算法也是广泛应用与推荐领域的算法,之所以称其为潜在因子,其原因在于这...

  • 丑数2

    描述 设计一个算法,找出只含素因子2,3,5 的第 n 大的数。 样例 代码实现

  • 信息化、计算机、网络安全题、法律法规

    1、网络安全题 RSA算法:是一种不对称算法、运算速度比DES慢、可用于数字签名方案、安全性主要基于素因子分析的难...

  • 去重算法_搬运

    去重算法用的情况比较多,自己就想做个记录,也方便以后自己看。算法是参照别人的,这里现附上 原地址:http://a...

  • js数组分组和去重

    分组 去重 笔试中经常出现的js数组排序与去重算法

  • 吃素

    一盘罗汉会三仙,汗出仙去莲花残。清淡因子艺未满,明朝闹海无素仙! 明朝闹海无素仙。

网友评论

      本文标题:算法训练 素因子去重

      本文链接:https://www.haomeiwen.com/subject/bgrnyqtx.html