首页 > 编程学习 > 蓝桥杯 算法训练 ALGO-190 素因子去重 JAVA

素因子去重

资源限制
时间限制:1.0s 内存限制:256.0MB

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

输入格式
一个整数,表示n
输出格式
输出一行,包含一个整数p。

样例输入
1000

样例输出
10

数据规模和约定
n<=10^12
样例解释:n=1000=2^353,p=2*5=10

//平平无奇的素因子拆分
public static void main(String[] args)
{
	Scanner sc = new Scanner(System.in);
	int x = sc.nextInt();
	StringBuilder str = new StringBuilder();
	int i = 2;
	while (i * i <= x)
	{
		if (x % i == 0)
		{
			while (x % i == 0)
			{
				str.append(i + " ");
				x /= i;
			}
		}
		// 素数 2 3 5 7 9 11 17 19...
		if (i == 2)
			i++;
		else
			i += 2;
	}
	if (x != 1)
		str.append(x + " ");
	System.out.println(x);
}
//这题ac代码
public static void main(String[] args)
{
	Scanner sc = new Scanner(System.in);

	long n = sc.nextLong();
	long x = 2;
	long mul = 1;
	while (x * x <= n)
	{
		if (n % x == 0)
		{
			while (n % x == 0)
			{
				n = n / x;
			}
			mul *= x;
		}
		if (x == 2)
			x++;
		else
			x += 2;
	}
	System.out.println(mul * n);
	//原本输出的时候要判断最后一个是不是1,但是题目要求是就因子的积
	//所以直接乘就好了
}
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000