[Java] 백준 11502 세 개의 소수 문제

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

난이도

실버 4

문제

정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다.

'5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 수도 있다.'

예를 들면,

7 = 2 + 2 + 3
11 = 2 + 2 + 7
25 = 7 + 7 + 11
5보다 큰 임의의 홀수를 입력받아서, 그 홀수가 어떻게 세 소수의 합으로 표현될 수 있는지 (또는 불가능한지) 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 T(Test Case의 수를 의미함)가 주어진다.

입력은 T개의 Test Case로 이루어진다.

각 Test Case는 하나의 정수 K (7 ≤ K < 1,000, K는 홀수)로 구성된다.

출력

T줄에 걸쳐서, 각 줄에 K가 어떻게 세 소수의 합으로 표현되는지 출력해야 한다.

가능하다면 그 세 소수를 오름차순 정렬하여 출력하면 된다.

여러 개의 답이 가능하다면 그 중 하나만 출력하면 되고, 만약 불가능하다면 0을 출력한다.

코드

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

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        boolean[] isNotPrime = new boolean[1001];
        ArrayList<Integer> prime = new ArrayList<>();

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        for(int i = 2; i * i <= 1000; i++){
            if(!isNotPrime[i]){
                for(int j = i * i; j <= 1000; j += i){
                    isNotPrime[j] = true;
                }
            }
        }

        for(int i = 2; i <= 1000; i++){
            if(!isNotPrime[i]) prime.add(i);
        }
        
        StringBuilder sb = new StringBuilder();
        int size = prime.size();
        
        for(int t = 0; t < T; t++){
            int N = Integer.parseInt(br.readLine());
            boolean find = false;
            
            for(int i = 0; i < size; i++){
                for(int j = 0; j < size; j++){
                    for(int k = 0; k < size; k++){
                        int a = prime.get(i);
                        int b = prime.get(j);
                        int c = prime.get(k);

                        if(a + b + c == N){
                            find = true;
                            sb.append(a + " " + b + " " + c + " " + "\n");
                            i = j = k = size;
                        }
                    }
                }
            }
            if(!find){
                sb.append(0 + "\n");
            }
        }

        System.out.println(sb);
    }
}