[백준 - 11653] 소인수분해
문제
소인수분해
소인수분해는 합성수💬 여러 소수들이 곱셈으로 합쳐져서 이루어진 수를 말한다. 를 소수들의 곱으로 나타내는 것을 말한다.
문제 풀이
풀이 1
가장 간단한 풀이 방법은 가장 작은 소수인 2부터 N까지 모든 수를 나누어 나머지가 0일 경우 그 값을 출력하는 것이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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;
}
}
}
}
위와 같이 구해도 문제없다. 하지만 이전 백준 문제인 소수찾기에서
“모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.”라는 걸 알았으므로 그것을 활용해 아래처럼 풀어보자.
풀이 2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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.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);
}
}
위의 풀이를 보면 마지막에 N != 1일 때 N을 한 번 더 출력해주는 조건문이 있다.
조건문을 넣어준 이유
for문으로 \(\sqrt{N}\)까지 나누고 남은 결과값이 2가지 케이스로 나뉜다.
예를 들어 N이 16이라면, 반복문으로 \(\sqrt{N}\)까지 나눈다면 i가 4까지 반복할 것이다.
처음에 2로 나누어 (16 % 2 == 0)이 되어 StringBuilder에 2를 넣어준다.
그리고 N을 2로 나누어 몫인 8이 N이 되고 다시 (8 % 2 == 0)이 되어 sb에 2를 넣어주고 몫인 4가 N이 된다.
이런 식으로 쭉 진행이 되어 마지막에 (2 % 2 == 0)이 만족되어 StringBuilder에 2를 넣고 2로 나눈 몫인 1이 N이 된다.
그리고 StringBuilder가 출력된다.
위에 적어둔 순서대로 문제없이 풀이가 진행된다.
하지만, 예외적인 조건이 있다.
다시 예를 들어 N이 58이라고 해보자. 반복문으로 \(\sqrt{N}\)까지 나눈다면 근사값이 약 5.71이므로 i가 5까지 반복할 것이다.
처음에 2로 나누어 (58 % 2 == 0)이 되어 StringBuilder에 2를 넣어준다. 그리고 몫인 29를 N에 넣을 것이다.
이제 여기서부터 문제가 발생한다. 29는 소수이기 때문에 자기 자신으로 밖에 나누어지지 않는다.
하지만 반복문은 5까지만 반복하므로 반복문이 종료되면 StringBuilder 안에는 2만 들어가 있기 때문에 2만 출력된다.
따라서 반복문이 종료된 후 N이 1이 아니라면 StringBuilder에 N을 넣어주는 조건문을 추가해야 한다.