[백준/BOJ] 9020번 : 골드바흐의 추측 - Java(자바)

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

9020번: 골드바흐의 추측

 

---

 

문제의 요구사항을 살펴보자.

(1) 중복이 허용되고

(2) 값 차이가 가장 작은

(3) 두 소수를 사용하여

(4) N을 조합하기

이다.

 

(3)과 (4)을 위해, N 이하의 소수들이 필요하다.

그래서 효율적으로 소수를 구할 수 있는 에라토스테네스의 체를 이용하기로 결심했다.

 

그런데 에라토스테네스의 체는 소수가 아닌 수까지 들어가 있다.

 

 

public static int[] getEratosthenes(int n) {
	int[] prime = new int[n + 1];

	for (int i = 2; i <= n; i++) prime[i] = i;
	for (int i = 2; i <= Math.sqrt(n); i++) {
		if (prime[i] == 0) continue;
        for (int j = i + i; j <= n; j += i) {
        	prime[j] = 0;
		}
	}
    
    return prime;
}

이로써 (3)은 만족되었다.

 

 

 

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

public class Main {
    public static int[] isPrime(int n) {
        int[] prime = new int[n + 1];

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

        return Arrays.stream(prime).filter(value -> value != 0).toArray();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(bf.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bf.readLine()), x = 0, y = 0;
            int min = n;
            int[] prime = isPrime(n);

            for (int j = 0; j < prime.length; j++) {
                for (int k = j; k < prime.length; k++) {
                    if (prime[j] + prime[k] == n) {
                        if (Integer.max(prime[j], prime[k]) - Integer.min(prime[j], prime[k]) <= min) {
                            x = prime[j];
                            y = prime[k];
                        }
                    }
                }
            }
            sb.append(x).append(' ').append(y).append('\n');
        }
        System.out.println(sb);
    }
}

 

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int t = Integer.parseInt(bf.readLine());

    for (int i = 0; i < t; i++) {
        int n = Integer.parseInt(bf.readLine()), min = n, x = 0, y = 0;
        int[] prime = isPrime(n);

        for (int j = 0; j < prime.length; j++) {
            if (min == 0) break;
            for (int k = j; k < prime.length; k++) {
                if (min == 0) break;
                if (prime[j] + prime[k] == n) {
                    if (Integer.max(prime[j], prime[k]) - Integer.min(prime[j], prime[k]) <= min) {
                        x = prime[j];
                        y = prime[k];
                        min = y - x;
                    }
                }
            }
        }
		sb.append(x).append(' ').append(y).append('\n');
    }
	System.out.println(sb);
}

import java.io.*;

public class Main {
    public static boolean[] isPrime(int n) {
        boolean[] prime = new boolean[n + 1];

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

        return prime;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(bf.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bf.readLine()), x = 0, y = 0;

            boolean[] prime = isPrime(n);
            int part1 = prime.length / 2, part2 = prime.length / 2;

            for (int j = 0; j <= prime.length; j++) {
                if (prime[part1] && prime[part2]) {
                    if (part1 + part2 == n) {
                        sb.append(part1).append(' ').append(part2).append('\n');
                        break;
                    }
                }
                part1--;
                part2++;
            }
        }
        System.out.println(sb);
    }
}

import java.io.*;

public class Main {
    public static int MAX = 10000;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean[] prime = new boolean[MAX + 1];

        for (int i = 2; i <= MAX; i++) prime[i] = true;
        for (int i = 2; i <= Math.sqrt(MAX); i++) {
            if (!prime[i]) continue;
            for (int j = i + i; j <= MAX; j += i) {
                prime[j] = false;
            }
        }

        int t = Integer.parseInt(bf.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bf.readLine());
            int part1 = n / 2, part2 = n / 2;
            
            for (int j = 0; j <= n; j++) {
                if (prime[part1] && prime[part2]) {
                    if (part1 + part2 == n) {
                        sb.append(part1).append(' ').append(part2).append('\n');
                        break;
                    }
                }
                part1--;
                part2++;
            }
        }
        System.out.println(sb);
    }
}