백준 6588 골드바흐의 추측 Java

정답률 27퍼센트의 소수관련 문제이다.

어떤 짝수 n은 홀수 소수를 더해서 만들 수 있다는 추측을 증명하는 문제이다.

입력으로 주어지는 짝수n를 홀수 소수 a와 b로  n = a + b 형태를 출력하면 된다.

 

정답률이 27퍼센트인 만큼 쉽지 않다.

에라토스테네스의 체로 소수를 구한다음에

for문 두개로 하나씩 비교하며 i+j == n 형태로 답을 구하면 시간초과로 틀리게 된다.

 

시간초과를 해결하기 위해 생각해봤지만 답은 나오지 않았다.

 

답은 for문을 한개 써서 해결하는 것이였다.

 

홀수인 소수들을 따로 빼서 새로운 배열을 하나만들고

소수인지 아닌지를 담아놓은 boolean형 배열 b에서

b[n-홀수인 소수]이면 출력을 하는 형태로 해결해야 했다.

 

입력으로 짝수 8이 들어왔다고 예를 들면

첫 번째 홀수인 소수 3부터 들어간다.

b[8-3] = b[5]

b[5] = true; //소수

3도 소수이고 5도 소수이기 때문에 정답이 된다.

짝수 - 홀수는 무조건 홀수 이기 때문에 홀수인지 검증도 안해도 된다.

 

이렇게 for문을 한번 써서 해결할 수 있다.

생각해내기 굉장히 어려운 방법이다.. 그래서 정답률이 20퍼센트 대 이겠지만

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        final int N = 1000000;
        boolean [] b = new boolean[N+1];
        List<Integer> list = new ArrayList<>();
 
        Arrays.fill(b, true);
 
        for(int i=3; i*i <= N; i+=2) {
            if(b[i]) //똑같은 배수를 돌 필요는 없다. i=4일 때 4의 배수는 2의 배수
                for(int j=i*i; j<=N; j+=i)
                    b[j] = false;
        }
        for(int i=3; i<=N; i+=2)
            if(b[i])
                list.add(i);
 
        while(true) {
            int n = scan.nextInt();
            boolean isWrong = true;
            if(n==0)
                break;
            for(int i=0; i<list.size(); i++)
                if(b[n-list.get(i)]) {
                    System.out.println(n+ " = " + list.get(i) +" + " + (n-list.get(i)));
                    isWrong = false;
                    break;
                }
            if(isWrong) //입력만 정상적이라면 틀릴 경우는 사실 없다.
                System.out.println("Goldbach's conjecture is wrong.");
        }
    }