백준[17103]번 : 골드바흐 파티션 ( JAVA )

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

17103번: 골드바흐 파티션

---

개발환경은 eclipse를 사용했습니다.

 

Code

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt(); // 테스트 케이스 입력받음

		boolean[] arr = new boolean[1000002]; // 논리형 배열 선언

		arr[0] = false;
		arr[1] = false; // 1은 소수로 생각하지 않음

		for (int i = 2; i < arr.length; i++) { // 2부터 배열크기만큼 소수라고 저장
			arr[i] = true;
		}

		for (int i = 2; i < arr.length; i++) {
			if (arr[i] == true) { // 소수일 경우 
				for (int j = i + i; j < arr.length; j += i) { // 배수들을 false로 저장
					arr[j] = false;
				}
			}
		}

		while (t-- > 0) { // 테스트 케이스 실행
			int n = sc.nextInt();
			int ans = 0;

			for (int i = 2; i < n; i++) { //2 부터 입력값까지 판별
				boolean q = arr[i];
				boolean p = arr[n-i];
				
				if (q && p && i <= n-i) { // i와 n-i를 더하면 n이므로 둘 다 소수일 경우와 중복을 방지하기 위한 조건
					ans++; // 출력 값 증가
				}
			}

			System.out.println(ans); // 출력
		}

		sc.close();

	}

}

---

처음에는 리스트를 이용해서 소수들을 찾아 contains를 사용해 풀었다

제출했더니 시간초과가 나서 방법을 알아보니 에라토스테네스의 체를 사용해서 푸는 문제였다.

 

코드에 주석을 보면 코드를 이해할 수 있을 것이다.

 

ans 값을 증가시킬 때 조건문에 중복을 방지하기 위해 i <= n - i를 사용한 점을 참고하면 좋겠다.