[백준] JAVA 자바 : 소인수분해 (11653번)

---

소인수 분해하는 문제이다. 소수 판정만 한다면 쉽게 풀 수 있을 것이다.
나같은 경우는 2부터 돌면서 소수인 수에 한해서 그 수로 나눠진다면 StringBuilder에 그 수를 담은 후 마지막에 출력했다.

근데 이렇게 돌리니까 180ms가 나오는데… 순위권에 계신 분들은 보면 70~80ms 언저리시다… 보면서 공부 좀 해야겠네…

 

import java.io.*;
import java.util.Arrays;

public class Factorization_11653 {
    
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = stoi(br.readLine());
        
        final int MAX = N;
        boolean[] n_list = new boolean[N + 1]; // 소수인지 아닌지를 담을 배열. true = 소수, false = 소수 아님
        
        Arrays.fill(n_list, true);
        n_list[0] = false;
        n_list[1] = false;
        for (int i=2; i<=Math.sqrt(MAX); i++) { // 2부터 돌면서
            if (n_list[i]) { // 만약 그 수가 소수라면
                for (int j=2; j*i<=MAX; j++) {
                    n_list[i*j] = false; // 그 수의 배수는 모두 합성수이다
                }
            }
        }
        // 여기까지가 1000000까지 모든 수가 소수인지 합성수인지 나타내는 배열인 n_list를 구성하는 과정!
        
        for (int i=2; i<=N/2; i++) { // 2부터 돌면서
            if (n_list[i]) { // 소수인 수에 한해
                while (N%i==0) { // 그 수로 N이 나눠진다면
                    sb.append(i).append("\n"); // StringBuilder에 그 수를 추가한다
                    N /= i;
                }
            }
        }
        
        if (N != 1) sb.append(N); // 남은 값도 StringBuilder에 추가해준다
        
        System.out.print(sb);
        
        br.close();
    }
}

 

로그인

 

 

작성일자: 2023-09-17