[Baekjoon] 11502_세 개의 소수 문제

Silver IV

문제(출처: https://www.acmicpc.net/problem/11502)

---

< 세 개의 소수 문제 >

 

문제 풀이 

 

모든 세 소수를 더해보며 가능한지 판단한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class _11502_ { // 세 개의 소수 문제

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(bf.readLine());

		boolean arr[] = new boolean[1000];
		arr[0] = true;
		arr[1] = true;
		for (int i = 2; i < 501; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 1000; j += i) {
					arr[j] = true;
				}
			}
		}

		for (int i = 0; i < t; i++) {
			int k = Integer.parseInt(bf.readLine());
			boolean flag = false;

			for (int a = 2; a <= k; a++) {
				if (!arr[a]) {
					for (int b = a; b <= k - a; b++) {
						if (!arr[b]) {
							if (!arr[k - a - b]) {
								bw.write(a + " " + b + " " + (k - a - b) + "\n");
								flag = true;
								break;
							}
						}
					}
					if (flag) {
						break;
					}
				}
			}
			if (!flag) {
				bw.write("0\n");
			}
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 수
arr : 소수 판단
k : 정수 
flag : 세 소수의 합으로 표현 가능 여부

 

테스트 케이스 수를 입력받는다. 먼저 2~999까지의 소수를 판단하여 arr에 소수 여부를 저장한다. 테스트 케이스 수만큼 정수 k를 입력받아 다음 과정을 반복한다.

 

1) a : 2부터 k까지 반복한다.

2) 만약 a가 소수라면 b : a부터 k-a까지 반복한다.

3) 만약 b가 소수라면 k-a-b가 소수인지 판단한다. k-a-b가 소수라면 그 값을 출력한 후 종료한다.

4) 세 소수의 합으로 표현되는 것이 불가능하다면 0을 출력한다.

---

---