完全平方数

题目

3491. 完全平方数 - AcWing题库

一个整数 $a$ 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 $b$，使得 $a=b^2$。

给定一个正整数 $n$，请找到最小的正整数 $x$，使得它们的乘积是一个完全平方数。

输入格式

输入一行包含一个正整数 $n$。

输出格式

输出找到的最小的正整数 $x$。

数据范围

对于 30% 的评测用例，$1≤n≤1000$，答案不超过 $1000$。
对于 60% 的评测用例，$1≤n≤10^8$，答案不超过 $10^8$。
对于所有评测用例，$1≤n≤10^12$，答案不超过 $10^{12}$。

输入样例1：
12
输出样例1：
3
输入样例2：
15
输出样例2：
15

思路：

就是枚举它能整除的平方数最后留下的就是最小数

例如$a=bbd(其中d不为平方数)$答案就是d，从而得出可以进行枚举，从$2$的平方数进行枚举。

代码

import java.util.*;

public class Main
{
    static long n;
    static int cnt = 0;
    final static int N = 100000010;
    static boolean[] is = new boolean[N];
    static int[] vis = new int[6000010];
    public static void isprime(int n)
    {
        for(int i = 2; i <= n; i ++)
        {
            if(is[i] == false)
                vis[cnt ++] = i;
            for(int j = 0; j < cnt && i * vis[j] <= n; j ++)
            {
                is[i * vis[j]] = true;
                if(i % vis[j] == 0)
                    break;
            }
        }
        return;
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextLong();
        for(long i = 2; i * i <= n; i ++)
        {
            while(n % (i * i) == 0)
                n /= i * i;
        }

        inScanner.close();
        System.out.println(n);
    }
}
/*
3 3
0 3
1 2
0 2
*/