[백준-Java] 기본수학 5, 6번

오늘 문제들도 모두 소수와 관련된 문제들이다.

대부분 에라토스테네스의 체를 이용하여 풀었고 큰 어려움은 없었다.

4번은 건너뛰고 5,6번을 설명하겠다.

4948번) 베르트랑 공준

문제 이름만 보고 겁나 어렵나보다...했었는데 별거 아니더라.

[자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. ]

이것만 구하면 되는데 핵심은
2n까지의 소수들을 추려내서 n부터 2n까지의 소수들을 count하면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T != 0){
            System.out.println(sosu(T));
            T = Integer.parseInt(br.readLine());
        }
    }
    public static int sosu(int n){
        int max = 2 * n;
        int count = 0;
        int[] arr = new int[max+1];
        for(int i = 2; i < max+1; i++){
            arr[i] = i;
        }
        for(int i = 2; i < max+1; i++){
            if(arr[i] == 0) continue;
            else{
                for(int j = i+i; j < max+1; j += i){
                    if(arr[j] == 0) continue;
                    else arr[j] = 0;
                }
            }
        } // 여기까지가 에라토스테네스의 체
        for(int i = n+1; i < max+1; i++){
            if(arr[i] != 0) count++;
        }
        return count;
    }
}

9020번) 골드바흐의 추측

이 문제 역시 크게 어렵지 않다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

위의 설명으로 볼때 모든 짝수는 두 소수의 합으로 이루어져있다고 볼 수 있다.

문제의 조건은 주어진 짝수를 두 소수의 합으로 나타낼 수 있는 것들 중에 가장 차이가 적은 두 소수를 찾아내는 것이다.

주어진 수를 반으로 나누면 간단하게 해결된다. 예를 들어,
16이면 (8,8)이고 두 수가 소수가 될 때까지 한 쪽을 줄여나간다면
(7,9) -> (6,10) -> (5,11) 이렇게 금방 찾을 수 있게 된다.

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

public class Main {
    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 N = Integer.parseInt(br.readLine());
            sosu(N);
        }
    }
    public static void sosu(int n){
        int count = 0;
        int big = 0;
        int sml = 0;

        int[] arr = new int[n+1];
        for(int i = 2; i < n+1; i++){
            arr[i] = i;
        }
        for(int i = 2; i < n+1; i++){
            if(arr[i] == 0) continue;
            else{
                for(int j = i+i; j < n+1; j += i){
                    if(arr[j] == 0) continue;
                    else arr[j] = 0;
                }
            }
        }
        for(int i = n/2; i > 1; i--){
            if(arr[i] != 0) {
                if(arr[n-arr[i]] != 0){
                    big = arr[n-arr[i]];
                    sml = arr[i];
                    break;
                }
            }
        }
        System.out.println(String.format("%d %d",sml,big));
    }
}

생각해 볼 것

9020번은 주어진 소수 중에서 값을 찾아내는 문제이다. 그러므로 값을 하나씩 줄여나가는 선형 검색보다 효율적인 방법이 있을 것이다.

그래서 이진 탐색를 생각해봤는데,
이진 탐색은 범위에서 계속해서 반을 나누어 필요한 범위로 계속 좁혀가는 기법이다.

위 문제의 경우에서 binary search를 쓰기가 까다로운 이유는
반을 나누었을때 큰 쪽으로 이어나갈지 작은 쪽으로 이어나갈지 정할 수가 없다는 점이다.

좀 더 효율적인 프로그램을 만들기 위해 더 생각해볼 가치가 있을 것 같다...