백준 16563번: 어려운 소인수분해 (G4)

문제

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

---

풀이 방법

소수를 구하는 효율적인 알고리즘에는 에라토스테네스의 체라는 것이 있다.

소수는 약수가 자기 자신과 1만 있는 숫자를 말하는데, 이것은 단순한 반복문으로도 구할 수는 있다.
하지만 다량의 소수를 한꺼번에 판별해서 구해야 할 경우에는 이야기가 달라진다.

많은 숫자들에 대해 일일이 판별하다 보면 실행시간은 한없이 길어질 것이다.

이 때 사용하는 알고리즘이 “에라토스테네스의 체(Sieve of Eratosthenes)” 이다.

마치 체처럼 걸러낸다고 하여 이름 붙인 이 알고리즘은, 2 이상 n 이하의 정수 x가 소수인지 아닌지 효율적으로 판단할 수 있도록 추가적인 배열을 만드는 전처리 알고리즘이다.

이를 이용해서 나타내면,

minFactor[x] : x가 갖는 가장 작은 소인수 값을 저장한다.

ex) minFactor[6] = 2

1. 미리 에라토스테네스의 체를 통해 1 ~ 500만 사이의 각 정수들의 가장 작은 소인수를 구한 후, 배열에 저장한다.
2. n개의 수를 입력 받는다.
3. 각 수를 가장 작은 소인수로 나누고 나누어 떨어지면 그 수를 해당 소인수로 나누고 소수를 출력한다.

---

코드

package day0209;

import java.io.*;
import java.util.*;

// 알고리즘 : "에라토스테네스의 체 "(소수/소인수분해를 구하는 효율적인 알고리즘)
// 2~n 정수 x가 소수인지 아닌지 판단 하거나, 
// x가 갖는 가장 작은 소인수 값을 minFactor[x]에 저장
public class BOJ_G4_16563_어려운소인수분해 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());	// 자연수 개수
		
		int[] minFactor = new int[5_000_001];
		
		for(int i=2; i<=5_000_000; i++) {
			minFactor[i] = i;
		}
		
		// 미리 각 자연수의 가장 작은 소인수를 저장해 둔다.
		for(int i = 2; i*i <= 5_000_000; i++) {
			
			if(minFactor[i] == i) {	// i가 소수라면
				for(int j = i*i; j <= 5_000_000; j += i) {	// 그 다음 큰 배수부터 전부 해당 소수로 표시 (각 자연수의 가장 작은 소인수 값이 저장됨)
					if(minFactor[j] == j) {
						minFactor[j] = i;
					}
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			int n = Integer.parseInt(st.nextToken());
			
			// 소인수 분해
			while(n > 1) {
				sb.append(minFactor[n] + " ");
				n /= minFactor[n];
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
}