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

혅·2024년 3월 23일

Java

1일1백준 -Java-

목록 보기

43/60

문제

정수론(수학)에서, 세 개의 소수 문제(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을 출력한다.

예제 입력

3
7
11
25

예제 출력

2 2 3
2 2 7
5 7 13

내가 했던 풀이 방법

입력받은 정수보다 작은 소수 list를 getPirme을 통해 찾는다. (더했을 때 입력한 정수가 되어야 하므로 정수보다 작은 소수만 찾아도 됨)
3중 for문을 통해 list에 들어있는 소수들을 조합하여 입력받은 정수가 되는 경우의 수를 찾고, 출력한다. 찾은 경우, has 변수를 true로 바꾼다. (has는 조건에 일치하는 경우가 있음을 의미하는 변수이다.)
모든 for문 끝에 has 변수를 검사하여, true일 경우 이후 검사를 진행하지 않도록 한다.
has가 false일 경우 0을 출력한다.

※ 소수 list 반환하는 메소드는 소수 관련 문제를 많이 진행하였으므로 설명을 생략.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cases = Integer.parseInt(br.readLine());
        
        int number;
        ArrayList<Integer> prime;
        for(int i=0; i<cases; i++) {
            number = Integer.parseInt(br.readLine());
            prime = getPrime(number);

            boolean has = false;
            for(int j=0; j<prime.size(); j++) {
                for(int k=0; k<prime.size(); k++) {
                    for(int l=0; l<prime.size(); l++) {
                        if(prime.get(j)+prime.get(k)+prime.get(l)==number) {
                            System.out.println(prime.get(j)+ " " + prime.get(k) + " " +prime.get(l));
                            has = true;
                            break;
                        }
                    }
                    if(has) break;
                }
                if(has) break;
            }

            if(!has) {
                System.out.println(0);
            }
        }
    }

    public static ArrayList<Integer> getPrime(int num) {
        ArrayList<Integer> prime = new ArrayList<>();

        boolean isPrime;
        for(int i=2; i<num; i++) {
            isPrime = true;
            if(i==2) {
                prime.add(i);
                continue;
            }
            for(int j=2; j<i; j++) {
                if(i%j==0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                prime.add(i);
            }
        }

        return prime;
    }
}