17103번 : 골드바흐 파티션 [Java]

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

17103번: 골드바흐 파티션

 

해결 방안

소수를 구하기 위해 에라토스테네스의 체를 사용한다.

 

주의할 점

각각의 테스트 케이스마다 소수를 구하면 시간 초과가 나오기 때문에, 테스트 케이스를 돌리기 전 소수를 구해두고 그걸 사용하도록 해야 한다. 두 소수의 순서만 다른 것은 같은 파티션임을 주의하자.

 

전체 코드

import java.util.Scanner;

public class Main {
	static boolean num[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// 소수 구하기 => 소수는 false
		num = new boolean[1000001];
		num[0] = num[1] = true;
		for (int i = 2; i * i <= 1000000; i++) {
			if (!num[i]) { // 소수를 찾으면
				for (int j = i + i; j <= 1000000; j += i) {
					num[j] = true; // 그 배수들은 소수가 아니다
				}
			}
		}
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			int temp = sc.nextInt();
			int ans = 0;

			for (int j = 2; j <= temp / 2; j++) {
				if (!num[j] && !num[temp - j])
					ans++;
			}

			System.out.println(ans);
		}
	}
}