[BOJ] 백준 1153번 네 개의 소수 (Java)

#1153 네 개의 소수

난이도 :  골드 4

유형 : 소수 / 골드바흐의 추측

1153번: 네 개의 소수

▸ 문제

임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다.

▸ 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

▸ 출력

첫째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다.

 

문제 풀이  

100만까지 소수의 개수는 78498개이다. 네 개의 수를 무작위로 짝 짓는 방식은 당연히 시간초과가 날 것이기 때문에 다른 방식을 사용해야 한다. 골드바흐의 추측을 이용하면된다. 골드바흐의 추측은 '2보다 큰 모든 짝수는 2개의 소수 합으로 표현할 수 있다.'이다. 그러면 어떤 수(num)가 나오든 짝수로 만들어준다면 그 어떤 수(num)은 무조건 소수의 쌍(prime1, prime2)로 분해가 가능하다는 소리이다.

 

그럼 남은 두 수는? (2, 2)와 (2, 3)으로 해결하면 된다. 만약 홀수가 주어진다면 (2, 3)의 소수를 먼저 짝지어주고 짝수가 나온다면 (2, 2)를 짝지어줌으로써 무조건 짝수로 표현하게 만든다. 그런 다음 에라토스테네스의 체로 가능한 소수를 모두 구한다음 두 수를 매칭시켜주면 된다. 그러면 O(N^2)으로 풀이가 가능하다.

 

풀이 코드 

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

public class Main {

	static int n;
	static boolean[] isPrime;
	static int[] ans = new int[4];
	static List<Integer> prime;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		isPrime = new boolean[n+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		prime = new ArrayList<>();
		artaos();
		
		if(n<8) {
			System.out.println(-1);
			return;
		}else {
			if(n%2 ==0) {
				n -= 4;
				goldbach(n);
				ans[0] = ans[1] = 2;
			}else {
				n -= 5;
				goldbach(n);
				ans[0] = 2;
				ans[1] = 3;
			}
		}
		
		for(int i=0; i<4; i++) {
			System.out.print(ans[i]+" ");
		}
	}
	
	static void goldbach(int num) {
		for(int i=0; i<prime.size(); i++) {
			for(int j=0; j<prime.size(); j++) {
				int sum = prime.get(i) + prime.get(j);
				if(sum == num) {
					ans[2] = prime.get(i);
					ans[3] = prime.get(j);
					return;
				}else if(sum > num) {
					break;
				}
			}
		}
	}
	
	static void artaos() {
		for(int i=2; i*i<=n; i++) {
			if(isPrime[i]) {
				for(int j=i*i; j<=n; j+=i) {
					isPrime[j] = false;
				}
			}
		}
		
		for(int i=2; i<=n; i++){
			if(isPrime[i]) prime.add(i);
		}
	}
}