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

블로그 이전, 2023. 5. 12. 18:52 에 작성했던 글입니다.

1.나의 풀이

1.에라토스테네스 체 만들기

public class Main {
    static boolean[] prime = new boolean[10001];
//에라토스테네스 체
    public static void prime() {

        /*소수 아님= true
          소수 =false
          */

        prime[0] = prime[1] = true;

        for (int i = 2; i < prime.length; i++) {
            if (prime[i] == true) continue;

            for (int j = i + i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
    }

prime 배열을 만든다.

• 4 ≤ n ≤ 10,000 조건이 있기 때문에 배열의 길이는 10001이다. 

소수 아님= true, 소수 =false로 설정했다. 후에 while문 조건이 true여야 수행되는데 소수가 아닐 때 while문이 계속 돌아야 하니까 소수가 아닐때를 true로 설정했다. 

 

0,1은 소수와 상관없으니까 true 로 설정

인덱스번호와 소수를 같게 한다. 후에 인덱스 번호로 소수를 구별해서 문제를 풀 수 있다. 

첫 번째 for문 돌면서 소수는 패스하고 두 번째 for문에서 소수의 배수들을 true로 하면서 소수 아님을 체크한다. 

첫 번째 for문에서 if문에 true가 나오면 이미 다 한 것이기 때문에 중단하고 다음으로 넘어간다.

예를 들어 i=4일 때 j는 8,12,16 이렇게 돌텐데  이미 i=2일 때 다 false가 되었다.

그래서  if (prime[i] == true) continue; 한 것이다. 

 

2. 소수 판별하고 출력하기

while (t > 0) {
            int n = Integer.parseInt(br.readLine());
            int p = n / 2;
            int q = n / 2;

            /*소수 아님= true
          소수 =false
          */

            while (true) {
                if (prime[p] == false && prime[q] == false) {
                    System.out.println(p + " " + q);
                    break;
                }
                p--;
                q++;
            }
            t--;
        }

8을 두 수의 합으로 나타내보면 이렇게 나온다.

7	1
6	2
5	3
4	4
3	5
2	6
1	7

골드바흐 파티션이 두 개가 나올 경우 그 차가 작은 것을 출력하라고 했다.

위의 표를 보면 4,4에 가까워질 수록 차가 적고 멀어질 수록 차가 커진다.

4,4를 기준으로 시작하면 제일 먼저 골드바흐 파티션이 되는 값이 자동으로 차가 적은 수가 되기 때문에

바로 출력하면 된다.

 

나는 처음에 4,4를 기준으로 앞 뒤가 같으니까 앞만 구해도 답이 나온다고 생각했다.

그래서 prime 배열의 길이를 5001을 했는데 (ArrayIndexOutOfBounds) 가 나왔다.

8일 경우 4,4가 while 문에 들어가고 true가 뜰 경우 p--, q++;을 하게 된다.

이 과정에서 ArrayIndexOutOfBounds가 발생한다. 그래서 배열의 길이는 10001이다. 

 

에라토스테네스 체를 2일 전에 배웠는데 활용을 잘 못하고 있다.

다른 문제들도 더 풀어봐야겠다. 

2.나의 코드

import java.io.*;

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

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

        prime();

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

        while (t > 0) {
            int n = Integer.parseInt(br.readLine());
            int p = n / 2;
            int q = n / 2;

            /*소수 아님= true
          소수 =false
          */

            while (true) {
                if (prime[p] == false && prime[q] == false) {
                    System.out.println(p + " " + q);
                    break;
                }
                p--;
                q++;
            }
            t--;
        }

        br.close();
    }

    //에라토스테네스 체
    public static void prime() {


        /*소수 아님= true
          소수 =false
          */

        prime[0] = prime[1] = true;

        for (int i = 2; i < prime.length; i++) {
            if (prime[i] == true) continue;

            for (int j = i + i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}