알고리즘

[BOJ] 2312 수 복원하기 - Java

Hzim 2023. 2. 11. 21:02

문제

https://www.acmicpc.net/problem/2312

 

2312번: 수 복원하기

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

www.acmicpc.net

 


풀이

  • 입력으로 들어온 수를 소인수분해한 후 인수와 인수의 횟수를 구한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(br.readLine());
            StringBuilder sb = new StringBuilder();
            for(int tc = 0; tc<T; tc++){
                int num = Integer.parseInt(br.readLine());
                for (int i = 2; i <= num; i++) {
                    int cnt = 0;
                    while (num % i == 0) {
                        num /= i;
                        cnt++;
                    }
                    if (cnt != 0) sb.append(i).append(" ").append(cnt).append("\n");
                    if (num == 0) break;
                }
            }
            System.out.println(sb);
    }
}
  • 소인수분해 후 인수를 구하고 횟수와 함께 stringbuilder에 추가