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

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

9020번: 골드바흐의 추측

---

---

주의점

• 2보다 큰 짝수에 대한 소수의 합 구하기
• 소수의 합이 여러 개일 때, 두 소수의 차이가 작은 경우 출력
• 두 소수 중 작은 수부터 출력

---

알고리즘

• 에라토스테네스의 체 활용

짝수 n에 대한 두 소수 구하기 + 두 소수의 차가 작은 경우 출력

• 예시

n = 14
n = p + q (p와 q는 소수)

14 = 7 + 7
14 = 3 + 11
➡ 두 소수의 차가 작은 7 7 출력해야

 

• 방법

짝수 n 절반으로 나누기

n = p + q (p와 q는 소수)

p와 q가 소수가 아니면 p는 1 감소, q는 1 증가시키기
(p와 q가 소수일 때까지 반복)

 

p	q	n = p + q	True / False
8	8	16	False
7	9	16	False
6	10	16	False
5	11	16	True
4	12	16	False
3	13	16	True
2	14	16	False

---

풀이

1. Scanner

import java.util.Scanner;
 
public class Main {
    //false: 소수, range: 0 ~ 10000
    public static boolean[] prime = new boolean[10001];
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
		
        get_prime();
 
        int T = in.nextInt(); //테스트 케이스
        while(T-- > 0) {
            int n = in.nextInt();
            int p = n / 2;
            int q = n / 2;
 
            while(true) {
                //두 파티션이 모두 소수일 경우
                if(!prime[p] && !prime[q]) {
                    System.out.println(p + " " + q);
                    break;
                }
                p--;
                q++;
            }
        }
    }
 
    //에라토스테네스의 체
    public static void get_prime() {
        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;
            }
        }
    }
}

 

2. BufferedReader

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    //false: 소수, range: 0 ~ 10000
    public static boolean[] prime = new boolean[10001];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        get_prime();
 
        int T = Integer.parseInt(br.readLine()); //테스트 케이스
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int p = n / 2;
            int q = n / 2;
 
            while(true) {
                // 두 파티션이 모두 소수일 경우
                if(!prime[p] && !prime[q]) {
                    System.out.println(p + " " + q);
                    break;
                }
                p--;
                q++;
            }
        }
    }
 
    //에라토스테네스의 체
    public static void get_prime() {
        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;
            }
        }
    }
}

 

3. BufferedReader + StringBuilder

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    //false: 소수, range: 0 ~ 10000
    public static boolean[] prime = new boolean[10001];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
		
        get_prime();
 
        int T = Integer.parseInt(br.readLine()); //테스트 케이스
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int p = n / 2;
            int q = n / 2;
 
            while(true) {
                //두 파티션이 모두 소수일 경우
                if(!prime[p] && !prime[q]) {
                    sb.append(p).append(' ').append(q).append('\n');
                    break;
                }
                p--;
                q++;
            }
        }
        System.out.print(sb);
    }
 
    // 에라토스테네스의 체
    public static void get_prime() {
        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;
            }
        }
    }
}

---

성능

1. BufferedReader + StringBuilder
2. BufferedReader
3. Scanner

 

---

출처 : https://st-lab.tistory.com/91