문제 번호 9020번 : 골드바흐의 추측 - JAVA [자바]

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

9020번: 골드바흐의 추측

문제 설명

 

골드바흐의 추측에 관련된 문제로 입력받은(무조건 짝수) 수를 만드는 합인 두 수를 구하는 문제입니다.

이때 두 수는 소수이여야 합니다.

 

문제 풀이

소수를 구하는 알고리즘은 에라토스테네스의 체 알고리즘을 사용했습니다. 이 알고리즘의 자세한 설명은 다음 게시물에 있습니다.

https://kkungchan.tistory.com/266

8단계 문제 번호 1929번 : 소수 구하기 - JAVA [자바]

이 문제는 두 가지 방법으로 풀어보겠습니다.

첫 번째는 로직을 통해서 해결하는 방법이고

두 번째는 수학적인 계산을 통해서 해결하는 방법입니다.

 

수학적으로 해결하는 것이 코드 길이가 짧고 가독성이 더 높습니다.

 

먼저 로직을 통해서 해결하는 방법입니다.

import java.util.Scanner;

public class Main {
    public static boolean[] primeCheck;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int loopNum = sc.nextInt();//반복할 수

        for(int loop=0; loop<loopNum; loop++) {

            int n = sc.nextInt();//짝수 n
            int gap = n;//치아가 작은 수를 찾기 위한 변수 가장 큰 차이인 n를 초기화 합니다.

            int primeNum1 = 0;//출력 할 소수 1
            int primeNum2 = 0;//출력 할 소수 2
            check_primNum(n);//n까지의 소수를 찾는 함수(에라토스테네스의 체 알고리즘)

            //소수가 2부터 시작임으로 2부터 시작한다.
            for (int i = 2; i < primeCheck.length; i++) {
                //i가 소수가 아닐경우 넘어간다.
                if (primeCheck[i] == true) {
                    continue;
                }

                //i가 소수일 경우 뺀 값을 계산한다.
                int remainder = n - i;

                //뺀 값이 소수가 아닐 경우 넘어간다.
                if (primeCheck[remainder] == true) {
                    continue;
                }

                //절대 값으로 gap보다 큰지 확인
                if (Math.abs(gap) >= Math.abs(remainder - i)) {
                    gap = remainder - i;//gap이 더 클 경우 작은 수를 gap에 초기화
                    primeNum1 = i >= remainder ? remainder : i;//해당 수를 출력할 변수에 초기화
                    primeNum2 = i <= remainder ? remainder : i;//해대아 수를 출력할 변수에 초기화
                }
            }

            System.out.println(primeNum1 + " " + primeNum2);
        }
    }

    public static void check_primNum(int n){
        primeCheck = new boolean[n+1];

        primeCheck[0] = primeCheck[1] = true;

        for(int i=2; i<Math.sqrt(n); i++){
            if(primeCheck[i] == true){
                continue;
            }

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

}

두 소수의 차이를 비교할 변수와 출력할 소수를 담을 변수 2개를 선언합니다. 

int gap = n;//치아가 작은 수를 찾기 위한 변수 가장 큰 차이인 n를 초기화 합니다.

int primeNum1 = 0;//출력 할 소수 1
int primeNum2 = 0;//출력 할 소수 2

 

받은 n의 수까지의 모든 소수를 구합니다. 함수에 대한 자세한 설명은 위에 게시해 들인 블로그에 보시면 있습니다.

check_primNum(n)

2부터 시작해서 소수인지를 체크합니다.

만약에 소수라면 해당 n에 소수만큼을 빼고 새로운 변수에 초기화해줍니다.

두 수에 차가 gap보다 작은 수라면 최종 출력할 변수에 입력한 후에 이 과정을 i->n까지 반복합니다.

//소수가 2부터 시작임으로 2부터 시작한다.
for (int i = 2; i < primeCheck.length; i++) {
    //i가 소수가 아닐경우 넘어간다.
    if (primeCheck[i] == true) {
        continue;
    }

    //i가 소수일 경우 뺀 값을 계산한다.
    int remainder = n - i;

    //뺀 값이 소수가 아닐 경우 넘어간다.
    if (primeCheck[remainder] == true) {
        continue;
    }

    //절대 값으로 gap보다 큰지 확인
    if (Math.abs(gap) >= Math.abs(remainder - i)) {
        gap = remainder - i;//gap이 더 클 경우 작은 수를 gap에 초기화
        primeNum1 = i >= remainder ? remainder : i;//해당 수를 출력할 변수에 초기화
        primeNum2 = i <= remainder ? remainder : i;//해대아 수를 출력할 변수에 초기화
    }
}

마지막으로 출력합니다.

System.out.println(primeNum1 + " " + primeNum2);

 

 

두 번째 방법은 계산을 사용하여 푸는 방법입니다. 위에 방법이 직관적이지만 코드가 길고 복잡합니다.

두번째 방법을 사용해서 코드의 가독성을 높여봅시다.

import java.util.Scanner;

public class Main {
    public static boolean[] primeCheck;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        //입력받는 t
        int t = sc.nextInt();
        
        //해당 소수를 찾기 위해 0부터 t까지 검사합니다.
        for(int i=0; i<t; i++){
            int n = sc.nextInt();

            check_primNum(n);//n까지의 소수를 찾는 함수(에라토스테네스의 체 알고리즘)
            
            /*
            결국 들어오는 수는 모두 2의 배수임으로 가장 차이가 작은 합은 n/2 + n/2 입니다.
            n/2가 소수라면 바로 그 수를 출력해도 됩니다.
            하지만 그 수가 아니라면 한수는 늘리고 한수는 줄여가며 가장 작은 차이의 소수를 구할 수 있습니다.
             */
            int firstPrimNum = n/2;
            int secondPrimNum = n/2;

            while(true){
                if(primeCheck[firstPrimNum] == false && primeCheck[secondPrimNum] == false){
                    System.out.println(firstPrimNum + " " + secondPrimNum);
                    break;
                }
                firstPrimNum--;
                secondPrimNum++;
            }
        }

    }

    public static void check_primNum(int n){
        primeCheck = new boolean[n+1];

        primeCheck[0] = primeCheck[1] = true;

        for(int i=2; i<Math.sqrt(n); i++){
            if(primeCheck[i] == true){
                continue;
            }

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

입력받는 수가 짝수라는 것을 이용해서 n/2 이가 제일 차가 작은 합이니 그 수부터 하나씩 늘리고 줄여가며 소수를 찾는 방법입니다.

자세한 사항은 주석에 기재해놓았습니다.