No.414 衝動

■■■問題■■■

あなたは突然、掛け算をしたい衝動に駆られました。どうしても今, 掛け算をしたいです。

掛け算してちょうどMになるような2つの自然数の組{x,y}を求めてください。
{1,M}, {M,1}はせこいので,1あるいはMを使ってはいけません。

ただし, どのような2つの自然数の組を使っても整数Mにならないときがあります。
そのときに限って,{1,M},{M,1}を使ってください。

■■■入力■■■

M

1行に整数Mが与えられます。ただし, 1 <= M <= 1兆 を満たします。
Mが32bit整数型に収まらないことがあるので注意してください。

■■■出力■■■

2つの自然数を半角空白区切りで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");
            //2 2
            //2×2 = 4 です。この他の解は存在しません
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("18");
            //6 3
            //6×3 = 18 です。
            //この他に {2,9}, {3,6}, {9,2} が考えられますが
            //どれを出力しても構いません。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            //1 2
            //1と2を使わずに2にする方法は存在しないので,
            //{1,2}, {2,1} のどちらかを出力します。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //偶数の場合
        if (M % 2 == 0) {
            Console.WriteLine("{0} {1}", 2, M / 2);
            return;
        }

        for (long I = 3; I * I <= M; I += 2) {
            if (M % I == 0) {
                Console.WriteLine("{0} {1}", I, M / I);
                return;
            }
        }
        Console.WriteLine("{0} {1}", 1, M);
    }
}

解説

試し割りで素数判定してます。