[백준 Baekjoon] 15711번 환상의 짝궁- JAVA

[백준 Baekjoon] 15711번 환상의 짝궁- JAVA

---

 

문제 풀이

문제의 설명만 보면 정말 간단한 문제처럼 보인다. A, B를 더한 값을 소수 2개로 만들 수 있는지 검사하면 된다. 하지만 제한사항의 A와 B의 최댓값이 2 x 10^12로 매우 커서 일반적인 방법으로는 불가능하다.

 

A와 B의 합이 최대 4 * 10^12로 범위가 매우 큰데 그것의 루트값 2000000으로만 검사해주면 된다..

 

합이 4미만의 경우

합이 4미만인 경우 소수 2개로 만드는 방법은 없다.

 

합이 짝수인 경우

골드바흐의 추축에 의하면 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다.

 

합이 홀수인 경우

두 수의 합이 홀수가 되려면 짝수 + 홀수이어야만 한다. 따라서 짝수인 소수 + 홀수인 소수로 동일한 합을 만들 수 있는지 찾아야 한다.

짝수인 소수는 2만 존재하기 때문에 합 - 2가 소수인지 검사하여 소수라면 만들 수 있다.

두 수의 합이 최댓값(2000000) 보다 작은 경우 에라토스테네스의 체로 소수인지 판별하고, 큰 경우 에라토스테네스의 체로 구해둔 소수들로 나누어지는지 검사한다. 소수로 나누어지면 소수가 아닌 수이다.

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static boolean[] isPrime = new boolean[2_000_001];
    public static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        eratosthenes();

        while (T-- > 0) {
            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 <= 2_000_000) 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] = true;

        for (int i = 2; i <= 2_000_000; i++) {
            if (!isPrime[i]) {
                list.add(i);
                for (int j = i * 2; j <= 2_000_000; j += i)
                    isPrime[j] = true;
            }
        }
    }
}