競プロおぼえがき

おぼえがきのためのブログ

yukicoder | No.414 衝動

  • 問題

No.414 衝動 - yukicoder

  • 概要

整数 Mが与えられるので x * y = Mとなる整数の組 \{x, y\}を求めて出力する。
ただし求める整数の組は \{1, M\}と\{M, 1\}以外のものでなければならない。
ただし \{1, M\}と\{M, 1\}以外の整数の組み合わせが見つからない場合は \{1, M\}と\{M, 1\}のどちらかを出力する。

  • 考え方

エラトステネスの篩を使って 2 ~ \sqrt{M}までの素数のリストを求める。
リストの要素 iでMが割り切れる \{i, M / i\}を出力する。
割り切れるものがなければ \{1, M\}を出力する。

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
       long n = in.nextLong();
       boolean[] pr = new boolean[(int)Math.sqrt(n) + 1];
       ArrayList<Integer> list = new ArrayList<>();
       for(int i = 2; i < pr.length; i++){
           if(pr[i]) continue;
           for(int j = 2 * i; j < pr.length; j += i){
               pr[i] = true;
           }
           list.add(i);
       }
       for(int i : list){
           if(n % i == 0){
               System.out.println(i + " " + n / i);
               return;
           }
       }
       System.out.println("1 " + n);
    }
}