[백준] 15711번 : 환상의 짝궁 Gold3(골드3) - JAVA[자바]

[Gold III] 환상의 짝꿍 - 15711

문제 링크

성능 요약

메모리: 18396 KB, 시간: 928 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2023년 12월 18일 16:00:43

문제 설명

환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이어붙이고 그 끈을 다시 길이가 소수인 끈 두개로 정확히 나눌 수 있다면 두 사람은 환상의 짝꿍이라고 한다. 하지만 그들은 길이가 소수인 두개의 끈으로 나눌 수 있는지 판단하는 것이 어려워서 대부분 서로가 인연임을 모르고 그냥 지나간다고 한다. 애석하게도...

그런 그들을 위해서 어떤 두 사람이 환상의 짝꿍인지 판단하는 프로그램을 작성하라.

편의상 두 사람의 끈을 이어붙일 때와 나눌 때 손실되는 끈의 길이는 0이라고 가정한다.

입력

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 500)가 주어진다.

둘째 줄부터 T개 줄에 두 사람이 가지고 있는 끈의 길이를 나타내는 정수 A, B가 공백으로 구분되어 주어진다. (1 ≤ A, B ≤ 2 × 10¹²)

출력

각 테스트 케이스마다 한 줄씩 두 사람의 끈을 이어붙이고 그 끈을 다시 길이가 소수인 두개의 끈으로 정확히 나눌 수 있다면 YES, 불가능하면 NO를 출력하라.

 

풀이 방법

1. 값의 합(Sum)은 짝수,홀수 두가지 경우로 나누어진다.

   a. Sum이 짝수인 경우 -> 골드바흐의 추측으로 짝수인 경우는 2를 제외하고 모두 소수의 합으로 표현이 가능하다.

   b. Sum이 홀수인 경우 -> 홀수는 짝수 + 홀수로만 표현이 가능하다. 짝수 소수는 2뿐이므로 (Sum - 2)가 소수인지 아닌지 판단하면된다.

2. S는 최대 4 * 10 ^ 12이기 때문에 Math.sqrt(4 * 10 ^ 12)인 2 * 10 ^ 6만 알고 있으면 Sum보다 큰 값이 들어오더라도 소수인지 아닌지 판단이 가능하다.

3. 2 * 10 ^ 6을 구해놓고 (Sum - 2)가 범위보다 작다면 바로 판단하고 그 이상이라면 소수들로 나누어보면 된다.

4. 예외로 4 이하라면 소수의 합으로 표현이 안된다. (4를 만들 수 있는 경우 (1,3)(2,2)) 바로 No를 출력

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

public class Main {
    static boolean[] prime = new boolean[2000001];
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        // 2 * 10 ^ 6만큼의 소수를 구해줌
        getPrime();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long sum = Long.parseLong(st.nextToken()) + Long.parseLong(st.nextToken());
            // 4이하라면 소수의 합으로 표현할 수 없기 때문에(1,3),(2,2) No출력
            if(sum < 4){
                sb.append("NO");
            }
            // 합이 짝수라면 골드바흐의 추측으로 소수의 합으로 출력이 가능하기 때문에 YES출력
            else if(sum % 2 == 0){
                sb.append("YES");
            }
            // 합이 홀수라면 짝수 + 홀수로 표현이 가능하다.
            // 짝수 소수는 2뿐이므로 sum-2가 소수인지 확인하면된다.
            else{
                if(checkPrime(sum-2)){
                    sb.append("YES");
                }else{
                    sb.append("NO");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void getPrime() {
        prime[0] = prime[1] = true;
        for (int i = 2; i < prime.length; i++) {
            if(prime[i]) continue;

            // 소수만 따로 구해주기위해서 List에 소수를 추가해준다.
            list.add(i);
            for (int j = 2 * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }

    private static boolean checkPrime(long sum) {
        // 만약 2 * 10 ^ 6의 범위보다 작다면 소수인지 아닌지 확인해준다.
        if(sum < prime.length) return !prime[(int)sum];

        // 그게 아니라면 2 * 10 ^ 6 밑 소수들로 나누어떨어지는지 확인
        // 나누어떨어진다면 sum은 소수가 아니다.
        for(int i = 0; i < list.size(); i++){
            if(sum % list.get(i) == 0){
                return false;
            }
        }
        return true;
    }
}