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

 

 

 

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

 

 

 

 

---

 

ㅇ 문제

 

 

입력한 수를 만족하는 소수의 합을 구하는 문제이다.

소수를 찾아야 하니 에라토스테네스의 체를 이용해여 접근한다.

 

 

---

 

◆ 핵심 아이디어

    1. 입력값까지의 소수를 구해야 한다.
    2. 입력값의 소수의 합을 출력한다.
    3. 소수의 합(골드바흐 파티션)이 여러 개일 경우, 두 소수의 차이가 가장 적은 것을 출력한다.
    4. 소수는 작은 것부터 출력한다.

 

 

 

◆ 에라토스테네스의 체

https://sfida.tistory.com/28

[Algorithm] JAVA 소수판별 - 에라토스테네스의 체

 

 

---

 

 

 

ㅇ 천천히 접근하기

 

1. 소수 찾기

먼저 에라토스테네스의 체 알고리즘을 이용하여 10000까지 소수를 찾을 것이다. 0부터 10000까지의 길이를 가져야 하니 prime 배열의 크기는 10001이다.

 

isPrirme의 경우, 에라토스테네스의 체 알고리즘이다. 위 링크의 에라토스테네스의 체 알고리즘을 숙지한 후, 코드를 읽으면 이해가 쉬울 것이다.

 

class Main {
    public static boolean[] prime = new boolean[10001];
    
    static void isPrime() {
        prime[0] = true;
        prime[1] = true;

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

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

 

 

 

2. 입력받기

 

테스트케이스 T를 입력하고, T의 개수만큼 숫자를 입력하도록 하였다.

 

import java.io.*;

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++) {
            int num = Integer.parseInt(br.readLine());
        }

    }

    static void isPrime() {
        prime[0] = true;
        prime[1] = true;

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

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

 

 

 

3. 골드바흐 파티션 구하기 (짝수 num에 대한 소수의 합)

 

먼저 isPrime()을 실행시킨 후, 소수를 판별한다.

 

res1과 res2는 최종 출력할 값이 할당되며, min과 abs는 소수의 값이 적은 것을 찾기 위해 할당되었다.

 

 

if(prime[j] || prime[num-j]) continue;

 > j와 num-j의 합은 num이다. 우리는 소수의 합이 num인 것을 찾아야 한다. 

 > j와 num-j는 하나라도 true가 나오면 안된다. false인 소수를 찾아야 하기 때문에 || 연산자를 넣어주었다.

 > continue로 인해 그 후의 코드는 j와 num-j가 소수인 것들만 남는다.

 

 

if(min>abs) {

    res1 = j;

   res2 = num-j;

   min = abs;

}

> 두 소수의 차의 절댓값이 min보다 작으면 최종 출력할 값은 j와 num-j가 되고 min은 abs로 변경된다.

> 이 과정을 통해 두 수의 차가 적은 것이 남게 된다.

 

 

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	// 소수 판별
        isPrime();

        int a = Integer.parseInt(br.readLine());
        for(int i=0; i<a; i++) {
            int num = Integer.parseInt(br.readLine());
            
            // 출력할 최종 골드바흐 파티션
            int res1 = 0, res2 = 0;
            
            // 골드바흐 파티션이 여러 개일 경우, 작은 것부터 출력하기 위한 변수 할당
            int min = 10000, abs = 0;
			
            // 2부터 1씩 증가하면서 소수의 합 탐색
            for(int j=2; j<num; j++) {
				
                // prime[j] 와 prime[num-j]가 하나라도 true(소수가 아닌 수)가 있으면 안되므로 
                // 뒤의 코드는 무시한다.
                if(prime[j] || prime[num-j]) continue;
				
                // 여기엔 소수만 남게 된다.
                
                // 두 소수의 차의 절댓값을 찾는다.
                abs = Math.abs(num-j-j);
                if(min>abs) {
                    res1 = j;
                    res2 = num-j;
                    min = abs;
                }

            }
            System.out.println(res1 + " " + res2);
        }

    }

    static void isPrime() {
        prime[0] = prime[1] = true;

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

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

 

 

 

 

 

---

 

 

 

ㅇ 최종 코드

 

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        isPrime();

        int a = Integer.parseInt(br.readLine());
        for(int i=0; i<a; i++) {
            int num = Integer.parseInt(br.readLine());
            int res1 = 0;
            int res2 = 0;
            int min = 10000, abs = 0;

            for(int j=2; j<num; j++) {

                if(prime[j] || prime[num-j]) continue;

                abs = Math.abs(num-j-j);
                if(min>abs) {
                    res1 = j;
                    res2 = num-j;
                    min = abs;
                }

            }
            System.out.println(res1 + " " + res2);
        }

    }

    static void isPrime() {
        prime[0] = prime[1] = true;

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

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

 

 

 

---

 

ㅇ 배운점

에라토스테네스의 체를 공부하면서 블로그에 정리한 적이 있다. 확실히 직접 기록하면서 습득하니 훨씬 기억에 오래 남았다. 이 글을 보고 공부한다면 직접 생각하고, 기록하면서 공부하는 것을 추천한다.

 

에라토스테네스의 다양한 유형을 풀어보면서 더 확실히 익혀야겠다.