이번 문제는 소인수분해를 하는 문제였습니다.
Step 0. 해답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Prime_Factorization {
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++) { // 2부터 N까지의 수를 1씩 늘려가면서 N과 나눠줘봄.
for (;;) {
if (N % i == 0) { // 딱 나눠진다면
N = N / i;
System.out.println(i);
} else {
break;
}
}
}
}
}코드 자체는 짧은데 생각보다 어려웠던 문제였습니다.
소인수분해의 정의와 산수의 기본정리에 의해 모든 합성수는 소인수분해된 형태를 갖는다는 내용 출처https://namu.wiki/w/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4
소수 목록 참고 출처 https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)
Step 1. 문제 접근
처음에는 숫자 N이 입력되면 2부터 시작해서 1씩 증가해서 나눠주도록 하였습니다. 이때 1씩 증가하는 나누는 값이 소수인지 확인 후 소수가 맞다면 나눠주는 작업으로 코드를 작성했는데 시간 초과가 떴습니다. 여기서 좀 더 찾아보니 나누는 값이 소인수인지를 확인할 필요가 없는 문제였습니다.
그 이유는 제가 이해한 대로 설명드리자면 소인수분해의 정의에서 소인수 분해는 합성수를 소수들의 곱으로 나타낸 것을 말합니다. 여기서 합성수란 소수가 아닌 수 입니다. 또한 모든 합성수는 소인수분해된 형태를 갖는다는 산술의 기본정리에서 증명된 조건을 갖고 있습니다. 예를 들어 18이 주어졌을 경우 6으로 나눈다고 생각해보면 6 3이 됩니다. 여기서 3은 소수이고 6은 합성수로써 기본 정의에 의하여 합성수는 소인수분해된 형태를 갖기에 무조건 소수로 나눌 수 있습니다. 그러면 결국엔 2 3 3이 남게 됩니다. 또한 가장 작은 수 2(1은 소수가 아니므로.)부터 1씩 늘리면서 나눠주면 2 > 3 > 4(나누기 2에서 처리 가능) > 5 > 6 (나누기 2에서 처리 가능) 7 > 8 (나누기 2에서 처리 가능) > 9 (나누기 3에서 처리 가능) ... 이런 식으로 자연스럽게 소수들로만 나누게 됩니다.(무슨 말이냐면 2부터 1씩 증가하면서 나누면 4나 6같은 수는 2의 배수이므로 2로만 최대한 나누면 4,6으론 나눠질 수 없습니다.)
식으로 해보자면 특정 수 N이 있고 N = a b이고 a는 소수 b는 합성수라고 가정할 때 b는 기본 정의에 의해서 b = c d형태로 변합니다. 여기서 c를 소수라고 한다면 d는 c를 제외한 모든 숫자들로써 소수일 수도 있고 합성수일 수도 있습니다. d가 소수라면 N = a c d(모두 소수)가 되고 합성수라면 또다시 소수와 합성수로 나누어지게 될 것입니다. 즉 낮은 수부터 나눠보면 결국은 소수들로만 나누게 된다는 소리입니다. 사람이 손으로 한다면 중간에 소수를 빼먹고 합성수로 나눌 순 있겠지만 컴퓨터이기에 이 걱정은 없습니다!
설명을 잘 못했는데 즉슨 그냥 2부터 1씩 증가하면서 딱 나눠지는 경우에만 나눠주면 소인수분해가 가능합니다!
Step 2. 문제 해결
1. 숫자 N을 입력받고 2~N까지의 숫자로 나눠줍니다. N을 포함한 이유는 N이 소수일 경우는 자기 자신과 나눠질 것이기 때문입니다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int i = 2; i <= N; i++) { // 2부터 N까지의 수를 1씩 늘려가면서 N과 나눠줘봄.2. 입력받은 N을 2부터 시작인 i와 나눠서 나머지가 0이면 나눠줍니다. 이때 2를 예로 들어서 , 해당 수 N이 소수 2로 1번만 나눠진다고 확실하게 말할 수 없으므로 나눠지지 않을 때까지 계속 나눕니다. 소수를 찾는 게 아니라 소인수분해를 하는 것이기 때문에 나머지가 0일 때 계산을 하고 출력하도록 하였습니다. 그 외의 경우는 break로 for문을 멈춰줬습니다.
for (;;) {
if (N % i == 0) { // 딱 나눠진다면
N = N / i;
System.out.println(i);
} else {
break;
}
}
}Step 3. 느낀 점
처음에는 나눌 숫자가 소수인지 아닌지를 확인해야하는 줄 알고 쉽게 풀었다가 시간 초과를 당한 문제였습니다. 알고리즘 자체는 어렵지 않으나 해당 개념을 이해하는데 살짝 생각을 해야 했던 문제였습니다. 중학교 과정에 처음 나오는 내용이던데 여러 정의라던지 아직도 소인수분해 관련 수식이 만들어지지 않았다는 사실등을 알게되어서 의외로 어렵다는 생각이 들었습니다.
출처 : 백준 11653번 https://www.acmicpc.net/problem/11653
