17103.골드바흐파티션

문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

## 입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

## 출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초	512 MB	20084	7692	5885	36.537%

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

풀이

코드

첫번째 시도

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  

public class 골드바흐파티션 {  


    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        boolean[] bool = new boolean[1000001];  
        Arrays.fill(bool, true); //bool의 기본값을 true로 변경.  

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

        for(int i=2; i<1000001; i++){  
            if(bool[i]){  
                for(int j=i+i; j<1000001; j=j+i){ //j=6 j=9 j=12 j=15 ... 반복  
                    bool[j] = false; //false면 소수가 아니다.  
                }  
            }  
        }  

        for(int i=0; i<t; i++){  
            int n = Integer.parseInt(br.readLine());  
            int count = 0;  
            for(int k=2; k<=n; k++){  
                for(int j=k; j<=n; j++){  
                    if(j + k == n && bool[k] && bool[j]){  
                        count++;  
                    }  
                }  
            }  
            System.out.println(count);  
        }  
    }  
}

결과적으로 실패....ㅠㅠ

3중 for문을 걸어준 부분이 문제가 되서 시간초과가 났다.

for(int i=0; i<t; i++){  
            int n = Integer.parseInt(br.readLine());  
            int count = 0;  
            for(int j=2; j<=n/2; j++){
                if(bool[j] && bool[n-j]) count++;
            } 
            System.out.println(count);  
            }
        }  

요렇게 처리해서 푸니까 정상적으로 동작하였다..!