No.300 平方数

■■■問題■■■

平方数とは、ある整数の2乗で表される整数である。
Xが与えられるので、

X * Y = Zの2乗 (X,Y,Zは1以上の自然数)
となるような最小のYを求めよ。

■■■入力■■■

X

1 <= X <= 100億

■■■出力■■■

X * Y が平方数になるような最小のYを1行に出力せよ。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("459431198626");
            //114514
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long X = long.Parse(InputList[0]);

        //平方数の倍数なら、その平方数で割る
        for (long I = 2; I * I <= X; I++) {
            long wkHeihouSuu = I * I;
            while (X % wkHeihouSuu == 0)
                X /= wkHeihouSuu;
        }
        Console.WriteLine(X);
    }
}

解説

平方数を約数に持ってたら、その平方数で割る処理を繰り返し、
最後の値が解となります。