11653 소인수분해

 

1. 풀이

 

다른 사람 블로그를 참고했다.

 

문제 예제에 나온 72를 가지고 설명하겠다.

 

1) 소인수 : 소수인 약수

즉 72를 소수인 약수들로 분해하면 된다.

 

2) 소수 : 약수가 1과 자기 자신뿐인 자연수

소수는 1이 아니라 2부터 시작한다.

 

 

단계 1

 

N = 72

 

72를 2로 나눈다.

나머지가 0이므로 2는 72의 인수이다. 그리고 소수이다.

=> 2를 출력

=> 72/2 = 36에 대해서 반복

 

 

단계 2

 

36을 2로 나눈다.

나머지가 0

=> 2는 36의 소인수

=> 2를 출력

=> 36/2 = 18 에 대해서 반복

 

 

단계 3

 

18을 2로 나누면 나머지가 0 

=> 2는 18의 소인수이다.

=> 2를 출력한다.

=> 18/2 = 9 에 대해서 반복

 

 

단계 4

 

9를 2로 나누면 나머지가 0이 아니다.

=> 2는 9의 인수가 아니다.

 

그러면 1을 증가시켜서 3으로 9를 나눈다.

나머지가 0

=> 3은 9의 소인수이다.

=> 3을 출력한다.

=> 9/3 = 3 에 대해서 반복

 

 

단계 5

 

3을 3으로 나누면 나머지가 0

=> 3은 3의 소인수

=> 3을 출력한다.

=> 3/3 =1 

 

1은 2보다 작은수이므로 더 이상 소인수 분해 할 것이 없다.

그래서 끝이 난다.

 

 

위의 과정을 보면

2,3,4 이런식으로 증가시키면서 N을 나누고, 

나머지가 0인지 여부로 인수를 판단한다.

 

하지만 4는 소수가 아니므로

N을 4로 나누는 경우는 생기면 안된다.

그런데 걱정할 필요없다.

 

위의 예제 72는 4의 배수이다.

4* 18 = 72 이기 때문이다.

하지만 앞에서 소수인 2가 72를 여러 번 나누기 때문에

72를 4로 나누어서 출력하는 경우는 생기지 않는다.

 

 

2. 최종 코드 

 

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 N = Integer.parseInt(br.readLine());
		
		for(int i=2; i<=N; i++) {
			while(N%i==0) {
				System.out.println(i);
				N/=i;
			}
		}
	}
}

 

참고 블로그 : 

 

https://st-lab.tistory.com/152

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