问题描述
给定一个正整数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;
}
}
内存超限
网友评论