• 문제: https://www.acmicpc.net/problem/15711

설명

이번 문제는 제한 사항의 A와 B의 최댓값이 2*10^12로 매우 크다는 점을 주의해야 한다.

• 또 바로 앞에서 푼 문제 골드바흐의 추측에서 2를 제외하고 S가 짝수인 경우 두 소수의 합으로 표현할 수 있다. 라는 증명을 기억해야 한다.
• 마지막으로 소수 중에 짝수는 2밖에 없음을 떠올려야 한다.

우리가 할 것은 A+B가 두 소수의 합으로 표현되는지 확인해야 한다.
1) A+B가 짝수인 경우

• 골드바흐의 추측에 의해 2를 제외한 모든 짝수는, 두 소수의 합으로 표현이 된다.

2) A+B가 홀수인 경우

• 짝수 + 홀수로만 표현이 가능하다.
• 소수 중에 짝수는 2밖에 없으므로 (A+B)-2가 소수인지 아닌지 판단한다.
  => 따라서 S가 최대 410^12여도 route(410^12)인 10^6이하의 소수만 알고 있으면 S가 큰 값이 들어와도 소수인지 아닌지 판단할 수 있다.

코드

public class P15711 {
	    public static boolean[] isPrime = new boolean[2000001];
    public static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P15711/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        eratosthenes();
        
        for(int i = 0; i < T; i++){
        	StringTokenizer st = new StringTokenizer(br.readLine());
            long A = Long.parseLong(st.nextToken());
            long B = Long.parseLong(st.nextToken());
            
            long sum = A + B;
            
            if (sum < 4) {
            	sb.append("NO").append("\n");
            } else if (sum % 2 == 0){
            	sb.append("YES").append("\n");
            } else {
            	if (check(sum-2)) {
                	sb.append("YES").append("\n");
                } else {
                	sb.append("NO").append("\n");
                }
            }
        }
    	System.out.println(sb);
	}
    
	public static boolean check(long x) {
    	if(x <= 2000000) {
        	return !isPrime[(int) x];
        }
        
        for(int i = 0; i < list.size(); i++) {
        	if(x % list.get(i) == 0) {
            	return false;
             }
         }
         
         return true;
    }    
    
    public static void eratosthenes() {
    	isPrime[0] = isPrime[1] = false;
        
        for(int i = 2; i <= 2000000; i++) {
        	if(!isPrime[i]) {
            	list.add(i);
                for(int j = i*2; j <= 2000000; j+= i){
                	isPrime[j] = false;
                 }
             }    
         }
     }
}     

• Reference: https://travelbeeee.tistory.com/493