[백준] 15711번 > 환상의 짝꿍

www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

문제

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

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

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

입력

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

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

출력

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

 

 

---

풀이

사실상 거의 수학문제였던 것 같다.. 단순하게 에라토스테네츠의 채를 사용하여 소수를 판별하고 해당 수를 소수로 표현할 수 있는지 판단하도록 구현을 했는데 시간초과 발생하였다.

A와 B의 범위가 10의 12승까지므로 굉장히 범위가 넓기 때문에 생각을 해야할 부분이 많다.

 

먼저 여기에는 골드바흐의 추측이 사용된다. 

골드바흐의 추측이란? 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

즉 이 문제에서 이를 적용시키면 4보다 큰 홀수만 판별해 내면 되는 것이다.

 

추가로 생각해야할 것이 홀수 = 짝수 + 홀수이다. 즉, 짝수인 소수는 2밖에 없으므로 해당 수 - 2가

소수라면 이는 두 소수의 합으로 나타낼 수 있음을 의미한다.

 

미리 구해놓은 소수값의 범위내라면 바로 소수인지 판단하여 값을 반환해주고 그 범위보다 크다면

소수로 나누어떨어지는지를 확인하여 소수판별을 진행한다.(소수로 나누어 떨어지면 소수 아님)

 

import sys
from math import sqrt
input=sys.stdin.readline

t=int(input())

max_num = 2000001
prime= [False, False] + [True for _ in range(max_num-1)]
for i in range(2,int(sqrt(max_num))+1):
    if prime[i]:
        for j in range(i+i,max_num,i):
            prime[j]= False 

sosu=[]
for i in range(2,max_num):
    if prime[i] == True:
        sosu.append(i)

def isPrime(n):
    if n > max_num:
        for s in sosu:
            if s >= n:
                break
            elif n % s == 0:
                return False
        return True
        
    else:
        return prime[n]


for _ in range(t):
    x , y= map(int, input().split())
    x += y
    if x < 4: 
        print('NO')
    elif x % 2==0: 
        print('YES')
    else:
        x -= 2
        if isPrime(x): 
            print('YES')
        else: 
            print('NO')