[Baekjoon] 17103_골드바흐 파티션

Silver II

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

---

< 골드바흐 파티션 >

 

문제 풀이 

 

에라토스테네스의 체를 활용하여 미리 소수를 판별해 둔다. 수를 입력받아 2부터 (입력받은 수/2)까지 탐색하여 소수의 합으로 나타낼 수 있는지 확인한다.

 

 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 _17103_ { // 골드바흐 파티션

	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[1000001];
		for (int i = 2; i < 500001; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 1000001; j += i) {
					arr[j] = true;
				}
			}
		}

		for (int i = 0; i < t; i++) {
			int num = Integer.parseInt(bf.readLine());
			int cnt = 0;

			for (int j = 2; j <= num / 2; j++) {
				if (!arr[j] && !arr[num - j]) {
					cnt += 1;
				}
			}
			bw.write(cnt + "\n");
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
arr : 소수 판별
num : 입력받은 정수
cnt : 골드바흐 파티션의 수

 

테스트케이스 수를 입력받는다. 먼저 에라토스테네스의 체를 사용하여 1000000까지 소수를 판별한다. 테스트케이스 수만큼 정수를 입력받는다. 2부터 (정수/2)까지 탐색하면서 소수의 합으로 나타낼 수 있는지 판별한다. 최종 골드바흐 파티션의 수를 출력한다.

---

---