9020) 골드바흐의 추측

문제 )                         https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

 

풀이 )

위의 문제는 여러가지 경우의 수중에서 두 수의 차가 작은 경우의 값을 구해야하므로

gap이라는 변수를 선언해서 문제를 풀었다.

입력받은 수 n = { (n/2) - gap } + { (n/2) + gap } 으로 볼 수 있으므로 

n을 입력 받은 뒤, 바로 n 에는 n/2 한 값을 대입했다. (->26번째 줄)

 

 

코드 )

import java.io.*;
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        boolean[] primeNum = new boolean[10001];
 
        for(int i=2; i<10001; i++) { // 2부터 N까지 전부 돌면서 검사
            for(int j=2; i*j<10001; j++) { // 소수가 아닌 수를 모두 true로 바꾸는 작업
                
                // 이미 검사가 되어 true 값이 들어갔다면 넘어감
                if( primeNum[i*j]) continue;
                
                // 아직 검사가 안된값이라면 true 값을 넣음
                // ex). i=2, j=2 이면 i*j=4 의값이 true가 됨
                primeNum[i*j] = true;
            }
        }
        
        int T = Integer.parseInt(br.readLine());
        while( T-- > 0) {
            
            int n = Integer.parseInt(br.readLine());
            n/=2;        // n = n/2 값을 저장함
            int gap=0;
            
            while( true ) {    //gap이 0일때부터 비교해서 가장 작은 차이를 찾으면 출력후 멈춤
                if( !primeNum[n-gap] && !primeNum[n+gap] ) {
                    bw.write( (n-gap) + " " + (n+gap) + "\n");
                    break;
                }
                gap++;
            }
        }
        br.close(); bw.flush(); bw.close();
    }
} cs