[백준 6588] 골드바흐의 추측

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

6588번: 골드바흐의 추측

---

1. 풀이

문제는 이해했지만, 풀이에 대해서 모호한 상태였는데 백준 강의를 통해 알게되서 정리한다. ( 갓 백준! )

 

우선, 골드바흐 추축의 의미는 '4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.' 와 같다.

 

이 말은 n = a(소수) + b(소수)라는 의미이고, 이는 다음과 같이 나타낼 수 있다. n - b(소수) = a(소수)

 

즉, 모든 소수를 구해놓고, check[n - b] = false면 출력하면 되는 문제였다.

 

---

2. 코드

import java.util.*;

public class Main {

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

        boolean[] check = new boolean[1000001];
        // 소수를 넣어놓는 리스트 (소수의 개수를 정확히는 모르기때문에 리스트로 넣는다.)
        ArrayList<Integer> prime = new ArrayList<Integer>();

        // 소수 찾기
        check[0] = check[1] = true;
        for(int i = 2; i < 1000001; i++){
            if(check[i] == false){
                prime.add(i);
                for(int j = i+i; j < 1000001; j+=i)
                    check[j] = true;
            }
        }
       
        while(true){
            int n = sc.nextInt();
            if(n == 0)
                break;
			
            // prime(소수)를 하나하나 꺼내면서 n과 뺐을때 소수인지 확인한다.
            for(int i = 0; i < prime.size(); i++){
                if(check[n-prime.get(i)] == false){
                    System.out.println(n+" = "+prime.get(i)+" + "+(n-prime.get(i)));
                    break;
                }
            }
        }
        sc.close();
    }
}