[BOJ][6588] 골드바흐의 추측

1. 문제 링크

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

2. 사용 알고리즘

에라토스테네스의 체

3. 풀이

1. 에라토스테네스의 체를 이용하여 1~1,000,000까지의 소수 구해서 배열에 저장

   • prime[i]

2. 소수 배열의 앞에서 부터 Loop를 돌며 num - prime[i]가 소수인 경우 출력

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/6588.cpp

#include <iostream>
#include <vector>

using namespace std;

vector<int> prime;
int check[1000003];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    check[1] = 1;
    for (int i = 2; i <= 1000000; ++i) {
        if (check[i] == 0) {
            prime.push_back(i);
            for (int j = i + i; j <= 1000000; j += i) {
                check[j] = 1;
            }
        }
    }
    int len = prime.size();
    while (1) {
        int num; cin >> num;
        if (num == 0) break;
        for (int i = 0; i < len; ++i) {
            if (check[num - prime[i]] == 0) {
                cout << num << " = " << prime[i] << " + " << num - prime[i] << "\n";
                break;
            }
        }
    }
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/6588.java

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

public class Main {

    static Vector<Integer> prime = new Vector<>();
    static int[] check = new int[1000003];

    public static void main(String[] args) throws IOException {
        check[1] = 1;
        for(int i = 2; i <= 1000000; ++i) {
            if(check[i] == 0) {
                prime.add(i);
                for(int j = i + i; j <= 1000000; j += i) {
                    check[j] = 1;
                }
            }
        }
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int len = prime.size();
        while(true) {
            int num = Integer.parseInt(br.readLine());
            if(num == 0) break;
            for(int i = 0; i < len; ++i) {
                if(check[num - prime.get(i)] == 0) {
                    sb.append(num).append(" = ").append(prime.get(i)).append(" + ").append(num - prime.get(i)).append("\n");
                    break;
                }
            }
        }
        System.out.println(sb);
    }
}