골드바흐의 추측

Day 42: 6588 (https://www.acmicpc.net/problem/6588)

---

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main
{
    public static boolean[] primes;
 
    public static void setPrimes(int size)
    {
        primes = new boolean[size];
        int sqrt = (int)Math.sqrt(size);
        for (int i = 2; i < sqrt; i++)
        {
            for (int j = i*2; j < size; j+=i)
            {
                primes[j] = true;
            }
        }
    }
 
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbl = new StringBuilder();
        setPrimes(1000000);
        int N = 0;
        
        while ((N = Integer.parseInt(br.readLine())) != 0)
        {
            int smallA = 0, bigB = 0;
            
            for (int i = 3; i < N; i+=2)
            {
                if (!primes[i] && !primes[N-i]) {
                    smallA = i;
                    bigB = N-i;
                    break;
                }
            }
            
            if (bigB == 0) sbl.append("Goldbach's conjecture is wrong.\n");
            else sbl.append(N).append(" = ").append(smallA).append(" + ").append(bigB).append("\n");
        }
        
        System.out.print(sbl);
    }
}

---

에라스토스테네스의 체를 이용해서 2~1,000,000의 소수를 구한 다음에, 3~N 범위 안의 홀수(i)를 체크하는 loop 안에서 N-i가 소수인지 확인한다. B-A가 가장 큰 상황을 제일 처음 접하기 때문에, 소수를 찾자마자 loop를 끝낸다.