[백준 / Java] 9020번 : 골드바흐의 추측

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

9020번: 골드바흐의 추측

 

---

◎ 문제

 

 

---

◎ 코드

 

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        // 테스트 케이스의 개수를 입력받는다.
        int T = sc.nextInt();
 
        // 소수 리스트를 생성한다.
        int [] primeList = new int[10001];
        for (int i = 0; i < 10001; i++) {
            primeList[i]=i;
        }
        primeList[1] = 0;
        for (int i = 2; i <= 10000 ; i++) {
            int k = 2;
            if (primeList[i] != 0) {
                try {
                    while(true) {
                        primeList[i*k]=0;
                        k+=1;
                    }
                } catch (Exception e) {
                    continue;
                }
            }
        }
 
        // 테스트 케이스의 개수만큼 반복해서 n을 입력받는다.
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
 
            // 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에 두 소수의 차이가 가장 작은것을 출력하기 위해
            // 두 변수(j,l)를 생성해 중간값부터 하나는 증가 하나는 감소시켜 그 두 값이 모두 소수이고 합이 n일 경우 출력한다.
            int l = n/2;
            for (int j = n/2; j < n; j--) {
                // j랑 l 둘 다 소수라면 출력
                if (primeList[j] == j & primeList[l] == l) {
                    System.out.println(j+" "+l);
                    break;
                }
                l+=1;
            }
        }
    }
}

 

---

◎ 풀이 및 기록

 

예전 소수를 구하는 문제에서 만들어둔 리스트를 활용하여 골드바흐 파티션을 구했다.

단, 파티션이 여러개일 경우를 대비해 n의 중간값부터 하나씩 증감하여 한번만 출력했다.