[백준 15711번] 환상의 짝꿍 (python, 소수, 에라토스테네스의 체, 골드바흐의 추측)

www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

m.blog.naver.com/PostView.nhn?blogId=rdd573&logNo=221270230610&proxyReferer=https:%2F%2Fwww.google.com%2F

 

위 글을 참고하여 풀었다.

 

골드 바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다는 것이다. 

따라서 홀수만 ! 체크해 주면 된다 

 

또 a,b의 범위가 워낙 커서 문제가 되는데 에라토스테네스의 체로 소수를 검사할 때 전체 수 m을 루트(m)만 검사해주면 되는 걸 감안해서 200만의 수만 에라토스테네스의 체로 걸러준다.

 

홀수만 검사할 때 홀수는 2+(어떤 수)로 나뉘게 되므로 어떤수=(홀수-2) 가 소수인지만 판별해주면 된다.

즉 홀수-2가 특정 소수의 배수만 아니라면 소수가 되기 때문에 기존에 구한 소수들로 나눠보고 소수인지 아닌지만 판별해주면 된다 

 

일단 나는 수학문제가 매우 싫다 ㅠ 푸는데 시간 좀 걸렸다

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

t=int(input())

# 골드 바흐의 추측: 2보다 큰 모든 짝수는 두개의 소수의 합으로 표시할 수 있다
# 따라서 3부터의 홀수만 체크해주면 된다.
mm=2000001
prime=[0]*mm # 0이면 소수
prime[1]=1 # 1은 소수가 아님
for i in range(2,int(sqrt(mm))+1):
    if prime[i]==0:
        for j in range(i+i,mm,i):
            prime[j]=1 # 소수 아님 체크

# 소수인 애들만 담아준다 (나중에 홀수-2인 수가 소수인지 판별할 때 쓴다)
q=[]
for i in range(2,mm):
    if prime[i]==0:
        q.append(i)

# 소수인지 
def is_prime(x):
# 소수인 애들로 나뉘게 되면 소수가 아닌 수이다.
    for i in range(0,len(q)):
        if q[i]*q[i]>x: break
        if x%q[i]==0: return 0
    return 1
for _ in range(t):
    x,y=map(int,input().split())
    x+=y
    if x<4: print('NO')
    elif x%2==0: print('YES')
    else:
    # 홀수-2
        x-=2
        # print(x,is_prime(x))
        if is_prime(x): print('YES')
        else: print('NO')