JAVA백준 문제풀이 (13) 9020: 골드바흐의 추측

 

백준 단계별 학습의 마지막 소수 문제이다.

늘 그랬듯이 에라토스테네스의 체로 해결한다.

 

 

https://7357.tistory.com/104?category=1065986 

0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체

 

 

평소보다 머리를 조금 더 써야하는데, 단순히 더해서 해당 값이 나오게 합만 구하면 되는 것이 아니라 여러 경우의 수가 있을 경우 최대한 소수의 차가 덜한 것을 구하라고 한다.

그렇다. 입력된 값을 반으로 갈라 중간부터 반복문을 돌리면 된다.

어차피 입력 값은 무조건 짝수기 때문에 반으로 나누는 것이 가능하다.

 

그리고 이번에는 마음 가는대로 작성한 지저분한 for문 버전과 다시 한 번 정리해서 작성한 while문 버전 두가지를 준비했다.

참고로 for와 while의 성능차이가 아니다. 둘은 그렇게 유의미한 성능차가 없다. 그저 내가 for문을 쓸데없이 2중으로 돌려서 생긴 문제일 뿐. for문 내부에 증감식을 두 개 만들어서 돌리면 while문과 비슷한 시간이 소요된다.

 

무조건 답만 맞추는 걸로 만족하지 말고 가독성과 성능을 신경 쓰며 풀 수 있도록 노력해야겠다.

 

 

 

1. for문 버전

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

public class Main {
    static boolean[] numArr = new boolean[10001];

    public static void main(String[] args) throws IOException {
        getPrimeNum();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for (int t=0; t<testCase; t++) {
            int inputNum = Integer.parseInt(br.readLine());
            loop : for (int i=inputNum/2; i<inputNum; i++) {
                for (int j=inputNum/2; j>0; j--) {
                    if (!numArr[i] && !numArr[j]) {
                        if ( inputNum - i - j == 0 )
                        {
                            System.out.println(j + " " + i);
                            break loop;
                        }
                    }
                }
            }
        }
    }


    // 소수 구하기
  static boolean[] getPrimeNum() {
     numArr[0] = numArr[1] = true;

     for (int i = 0; i*i < numArr.length; i++) {
         if ( !numArr[i] ) {
             for (int j = i*i; j < numArr.length; j+=i ) {
                 numArr[j] = true;
             }
         }
     }

     return numArr;
 }
}

 

 

2.  while 버전

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

public class Main {
    static boolean[] numArr = new boolean[10001];

    public static void main(String[] args) throws IOException {
        getPrimeNum();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        while ( testCase-- > 0 ) {
            int inputNum = Integer.parseInt(br.readLine());

            int index1 = inputNum/2;
            int index2 = inputNum/2;

            for (;;) {
                if ( !numArr[index1] && !numArr[index2] ) {
                    System.out.println(index1 + " " + index2);
                    break;
                }
                index1--;
                index2++;
            }
        }
    }


    // 소수 구하기
  static boolean[] getPrimeNum() {
     numArr[0] = numArr[1] = true;

     for (int i = 0; i*i < numArr.length; i++) {
         if ( !numArr[i] ) {
             for (int j = i*i; j < numArr.length; j+=i ) {
                 numArr[j] = true;
             }
         }
     }

     return numArr;
 }
}