[백준] 소인수분해_11653_자바

11653번 Java - 소인수분해

---

이번 문제의 분류는 <기본 수학 2>에 해당합니다.
소인수분해는 중등 과정에서 한 번씩 배운 내용입니다. 그래서인지 기억이 가물가물 하네요.😂

---

소인수분해는 이름 그대로 어떤 자연수를 소인수로 분해한 것입니다.

나눗셈 과정을 보겠습니다.

(나눠지는 수) ÷ (나누는 수) = (몫) + (나머지)

약수는 나눗셈에서 나머지가 0일 때 (나누는 수)를 말합니다. 즉, 나눠지는 수의 약수입니다.

약수는 여러 개가 있을 수 있습니다. 이때 나누는 수와 몫은 나눠지는 수의 인수에 해당합니다.

예를 들면 나눠지는 수가 30일 때, 인수는 1, 2, 3, 5, 6, 10, 15, 30입니다.

이제 소수를 알아보겠습니다.

소수는 1과 자기 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수를 말합니다.

2, 3, 5, 7, 11, 13,, 과 같은 수들이 소수에 해당합니다.

위 예시에서 30의 인수들을 봤을 때 2, 3, 5가 소수입니다.

그리고 소인수 분해는 이러한 소수들의 곱으로 표현합니다. 30을 소인수 분해하면 2 X 3 X 5가 되는 것입니다.

소인수분해에 대해서 간략하게 알아봤으니 이제 코딩 테스트 문제를 풀어보도록 하겠습니다.

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

11653번: 소인수분해

---

1. 문제

정수 N이 주어졌을 때, 소인수 분해하는 프로그램을 작성하시오.

2. 예제

---

3. 풀이

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

import static java.lang.Math.sqrt;

public class Main {
	public static void main(String[] args) throws IOException {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 소인수분해할 수 입력
        int N = Integer.parserInt(br.readLine());
        
        // sqrd 메소드는 파라미터의 양의 제곱근 반환
        for(int i = 2; i <= sqrt(N); i++) {
        	while(N % i == 0) {
            	sb.append(i).append('\n');
                N / i;
            }
        }
        if (N != 1) {
        	sb.append(N);
        }
        System.out.println(sb);
	}
}

1) StringBuilder를 통해서 반복문 안에서 출력되는 값을 한 번에 출력합니다.

2) N의 인수들을 보면, 두 인수 중 한 개 이상은 반드시 √N 보다 작거나 같습니다.

예를 들어서 30의 제곱근은 약 5.47 정도입니다.
그리고 인수를 나열하면 1, 2, 3 ,5 ,6 , 10, 15, 30입니다.
2X15, 3X10, 5X6과 같이 인수 중 한 수는 30의 제곱근보다 작다는 것을 알 수 있습니다.

따라서 for문에서 N까지 반복할 필요 없이 제곱근 이하로만 반복하면 됩니다.

이는 Math 클래스의 sqrt 메서드를 활용하여 N의 양의 제곱근을 구할 수 있습니다.

3) 2부터 √N까지 모든 수를 나누면서 나머지가 0일 경우 그 값을 출력합니다.( 1은 소수에 해당 x )

72 소인수분해 과정

만약 N을 i로 나누었을 때 나머지가 0이라면, 해당하는 i를 append 해줍니다. 이어서 N을 i로 나눕니다.
N/i 가 또 한 번 i로 나눴을 때 나머지가 0이라면 동일하게 과정을 진행합니다.
만약 0이 아니라면, for문을 통해 i값을 1 증가시켜 앞과 동일하게 과정을 진행합니다.

4) 반복문이 끝나고 소인수분해가 된 N은 값이 1이 되어 있습니다. 하지만 그렇지 않은 경우도 있습니다.

예를 들어서 34를 입력하고 반복했다면, N은 17이 될 것입니다. 이는 17이 소수이기 때문에 그렇습니다. 
그렇다면 소인수분해를 통해 2, 17이 출력되어야 합니다. 따라서 if문을 통해 N이 1이 아닐 때 현재 N 값을 추가로 출력해줍니다.

---

4. 결과