[Java] 백준 2247번 : 실질적 약수

문제

15711번: 환상의 짝꿍

---

접근 방법

1. A+B를 이어붙이고 이 끈을 나누었을때 소수인 두개로 나눌 수 있는지 판단하는것이었습니다.

2. 두 끈을 이어붙였을때 2부터 ~4 * 10^12 승까지 가능하고, 2와 3은 어떻게 나누어도 소수 두개로 이루어질 수 없으므로 NO를 출력합니다.

3. 4이상일때 짝수와 소수로 나누어 질 수 있는데 짝수일 경우 어떻게 나누어도 소수 2개로 나눌 수 있습니다. (골드바흐의 추측)

4. 홀수는 짝수+홀수 이므로 짝수중 제일 작은 소수인 2를 왼쪽 끈으로 주고, 오른쪽이 소수인지만 체크하면 됩니다.

5. 소수는 자신의 제곱근 범위까지 확인하면 되기 때문에 4*10^12 승의 제곱근인 2*10^6 = 2,000,000 까지 소수를 구하고, 이 범위가 넘어가면 소수를 이용하여 체크하면서 소수인지 판단합니다. 만약 소수로 나누었을때 나누어진다면 그것은 합성수 이므로 소수가 아니기 때문에 false를 리턴 (ex. 6 % 2 = 0 -> 6은 소수가 x) 해 줍니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int T;
    private static long A,B;
    private static ArrayList<Integer> list = new ArrayList<Integer>();
    private static boolean[] isPrime = new boolean[2000010];
    
    public static void eratosthenes(){
        isPrime[0] = isPrime[1] = false;

        for(int i = 2 ; i < 2000000 ; i++){
            if(!isPrime[i]) continue;

            list.add(i);

            for(int j = i*2 ; j < 2000000 ; j += i){
                isPrime[j] = false;
            }
        }

    }

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

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

        Arrays.fill(isPrime,true);
        eratosthenes();

        for(int tc = 0 ; tc<T ; tc++){
            st = new StringTokenizer(br.readLine());

            A = Long.parseLong(st.nextToken());
            B = Long.parseLong(st.nextToken());
            process(A+B);
        }
    }
    
    //소수 체크
    public static boolean check(long input){
        if(input <= 2000000){
            return isPrime[(int)input];
        }

        for(int i = 0 ; i < list.size() ; i++){
            if(input % list.get(i) == 0 ){
                return false;
            }
        }
        return true;
    }

    //실행
    public static void process(long sum) {
        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");
            }
        }

    }


    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}