[백준] 11653번 소인수분해 - Java, 자바

난이도

실버 5

문제

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

코드

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

// 11653번 소인수분해
public class boj_4_11653 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for(int i =2;i<=Math.sqrt(N);i++) {
            while (N % i == 0) {
                sb.append(i).append('\n');
                N/=i;
            }
        }

        if(N!=1){
            sb.append(N);
        }
        System.out.println(sb);

    }
}

풀이

소인수분해란 어떤 수를 소수인 인수로 분해하는 것

가장 쉬운 방법

for(int i = 2; i <= N; i++) {
	while(N % i == 0) {
		println(i);
		N /= i;
	}
}

2부터 N까지 모든 수를 나눠보며 나머지가 0일 경우 그 값을 출력

좀 더 효율적인 방법
어떤 N이 두개 이상 곱셈으로 나타낼 수 있을 때 인수중 한개 이상은 반드시 루트 N보다 작거나 같다.
따라서, 반복문의 범위를 루트 N까지 반복

for(int i = 2; i <= sqrt(N); i++) {	// 또는 i * i <= N
	while(N % i == 0) {
		println(i);
		N /= i;
	}
}
 
if(N != 1) {
	println(N);
}

이때 중요한 점은 N/=i로 나누고 남은 최종 N이 두가지 케이스로 나뉜다.

N=16일 때, 루트 N까지 반복한다면 4까지 반복
16%2=0, 8%2=0, 4%2=0, 2%2=0 2/2=1

N=34일 때, 루트 N까지 반복한다면 5까지 반복
34%2=0, 34/2=17
17이라는 인수를 출력 못하고 종료되어버리는 문제를 막기 위해 아래를 추가

if(N != 1) {
	println(N);
}