[python] 백준 15711 환상의 짝궁

https://www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

 

문제 해결

• 시간과 메모리 모두 빡빡한 문제이다.
• A, B 가능한 숫자가 $10^{12}$를 넘어가기 때문에 줄여서 계산해야한다.
• 골드바흐의 추측 (2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.)를 생각해야한다.(2이면 1+1이므로 "NO"출력 2보다 큰 짝수는 "YES"출력 하면 된다.
• 3은 'NO'임을 알 수 있고 5이상의 홀수 x 는 x= 2 + (x-2)로 나타낼 수 있다. x-2가 소수인지 아닌지 확인하면 된다.
• 에라토스 테네스 체를 사용해야하는 것은 쉽게 알 수 있다. 다만 숫자가 크므로 어떻게 효율적으로 사용할 것인지 생각해야한다.
• $ 2*10^{12}$ 의 제곱근까지 소수를 모두 저장하는 리스트를 만든다.
• 그 안에 있는 수 중 하나라도 x-2를 나누어 나머지를 0으로 만들 수 있다면 소수가 아니고 어떤 수도 나머지를 0으로 못만들면 소수이다.
• 이렇게 해도 python3로는 시간초과가 난다...ㅜㅜ(pypy3로는 가능)
• 다른 풀이는 찾아봤는데 없는 것 같다.(ㅜㅜ)

 

CODE

import math
def is_prime(num):
    for i in range(0,len(q)):
        if q[i]*q[i]>num: break
        if num%q[i] ==0:
            return False
    return 1
    
if __name__=='__main__':
    max_test = 1500001 # 2 × (10**12) 의 제곱근 값까지만 검사하면 됨
    prime = [1]*max_test
    prime[0] = 0
    prime[1] = 0
    for i in range(2,int(math.sqrt(max_test))+1):
        if prime[i] ==1:
            for j in range(i+i,max_test,i):
                prime[j] = 0   
    q = []
    for i in range(2,max_test):
        if prime[i] == 1:
            q.append(i) 
    for _ in range(int(input())):
        x = sum(map(int, input().split()))
        if x<4:
            print("NO")
        elif x%2==0:
            print("YES") # by 골드바흐의 추측
        else:
            if is_prime(x-2):
                print("YES")
            else:
                print("NO")