백준 9020번 골드바흐의 추측 JAVA

링크텍스트

설명

에라토스테네스의 체 + 투 포인터
시간복잡도: O(NloglogN+T×n), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());

        boolean [] num = new boolean[10001];
        for(int i=2;i<=Math.sqrt(10000);i++){
            if(!num[i]){
                for(int j=i*i;j<=10000;j+=i){
                    num[j] = true;
                }
            }
        }
        //num[2] = false;

        while(t-->0){
            int n = Integer.parseInt(br.readLine());

            if(n==4){
                sb.append("2 2").append("\n");
                continue;
            }else if(n==6){
                sb.append("3 3").append("\n");
                continue;
            }

            int start = 2;
            int end = n-3;

            int i=0,j=0;
            int abs = 10000;

            while(start<=end){
                if(!num[start] && !num[end] && start+end==n){
                    if(Math.abs(start-end)<abs){
                        i=start;
                        j=end;
                    }
                    end-=2;
                }else if(start+end>n){
                    end-=2;
                }else start++;
            }

            sb.append(i+" "+j).append("\n");
        }

        System.out.print(sb);
    }
}

• 777문제 해결한 날

최적화 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        // 에라토스테네스의 체
        boolean[] isComposite = new boolean[10001];
        isComposite[0] = isComposite[1] = true;

        for(int i=2;i*i<=10000;i++){
            if(!isComposite[i]){
                for(int j=i*i;j<=10000;j+=i){
                    isComposite[j] = true;
                }
            }
        }

        while(T-->0){
            int n = Integer.parseInt(br.readLine());

            int a = n/2;
            int b = n/2;

            while(true){
                if(!isComposite[a] && !isComposite[b]){
                    sb.append(a).append(" ").append(b).append("\n");
                    break;
                }
                a--;
                b++;
            }
        }

        System.out.print(sb);
    }
}