[백준 알고리즘] 1153번 네 개의 소수 (Java)

스페셜저지: 예제 출력 외에도 답이 존재한다.

풀이방법

1. 네 개의 소수 합 -> 두 개의 소수 합 + 두 개의 소수 합
   -> 골드바흐의 추측 을 사용

참고용 : 골드바흐의 추측

https://velog.io/@yeoj1n/백준-알고리즘-9020번-골드바흐의-추측

2. 가장 작은 소수는 2이므로 2 * 4 = 8, 8보다 작은 수는 네 개의 소수 합을 만들 수 없으므로 -1 을 리턴시킨다.
3. 8보다 큰 수는 짝수, 홀수로 나누고

홀수의 경우 네 개의 소수 중 두 소수가 2,3 이라고 가정한 후 입력 값 N - 5 에 골드바흐의 추측을 적용하여 나머지 두 소수를 구한다.
짝수의 경우 네 개의 소수 중 두 소수가 2,2 라고 가정한 후 입력 값 N - 4 에 골드바흐의 추측을 적용하여 나머지 두 소수를 구한다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

// 네 개의 소수 
public class Main {
	final static int[] prime = new int[1000001];
	
	// 짝수 한 쌍 만들고 각각 골드바흐의 추측을 적용 
	public static void main(String[] args) throws Exception {
		setPrime();
		ArrayList<Integer> list = new ArrayList<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		if(num < 8) {
			System.out.println(-1);
			return;
		} else{
			if(num % 2 == 1) {// 홀
				list.add(2);
				list.add(3);
				list.addAll(goldBach(num - 5));
			} else { // 짝
				list.add(2);
				list.add(2);
				list.addAll(goldBach(num - 4));
			}
			
			Collections.sort(list);
			StringBuilder sb = new StringBuilder();
			for(int n : list)
				sb.append(n + " ");
			System.out.println(sb.toString().trim());
		}
	}
	
	public static ArrayList<Integer> goldBach(int num) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i=2; i<=num/2; i++) {
			if(prime[i] == 0 && prime[num-i] == 0) {
				list.add(i);
				list.add(num-i);
				break;
			}
		}
		return list;
	}
	
	public static void setPrime() {
		for(int i=2; i*i<=1000000; i++) {
			for(int j=i*i; j<=1000000; j+=i) {
				prime[j] = -1;
			}
		}
	}
	
}