[백준] 15711 환상의 짝꿍 python (*)

문제

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

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

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

입력

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

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

출력

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

코드

#15711
import sys

# 에라토스테네스의 체
# n = 2*(10**12) +1 # 끈의 길이 메모리 초과 따라서 절반만 에라토스테네스의 체 수행
n = 2*(10**6) + 1
arr = [True for _ in range(n)]
primes = [] # 소수
for i in range(2,n):
    if arr[i]:
        primes.append(i)
        for j in range(2*i, n, i):
            arr[j] = False

# 소수인지 판별
def isPrime(x):
    if x > n: # x 가 n인 2*10**12 보다 크면
        for prime in primes:
            if prime >= x:
                break
            elif x % prime == 0:# 소수로 나뉘는지로 판별
                return False
        return True
    else: # x가 n보다 작으면 바로 소수에서 꺼내기
        return arr[x]

# 테스트케이스
t = int(sys.stdin.readline())
for _ in range(t):
    ab = sum(map(int,sys.stdin.readline().split()))

    # 골드바흐의 추측 : 4보다 큰 짝수는 두 홀수 소수의 합으로 가능하다.
    # 4 보다 작으면 NO
    if ab < 4 :
        print("NO")
    # 4보다 큰 짝수 YES
    elif ab % 2 == 0:
        print("YES")
    else: # 홀수는 2(짝수 소수) + 홀수 소수의 합으로 가능하다. -> 홀수-2 가 소수인지 확인
        if isPrime(ab-2):
            print("YES")
        else:
            print("NO")

풀이

간단하게 에라토스테네스의 체로만 풀면 시간초과 난다.

문제에서 알고 있어야 할 것이 에라토스테네스의 체와 골드바흐의 추측이다.

근데 이렇게 풀어도 python으로는 시간초과가 나서 pypy3로 제출했다.

빠르게 풀 수 있는 방법 아시는분?

 

1) 체의 범위가 2*10**12나 되기 때문에 그 절반만 에라토스테네스의 체를 우선적으로 만들어주고

소수판별을 원하는 수가 이 범위보다 크면 소수로 나뉘는지로 판별한다.

 

2) 골드바흐의 추측 :  4보다 큰 짝수는 두 홀수인 소수의 합으로 가능하다.

따라서 4보다 작으면 NO 크면 짝수면 YES

4보다 큰 홀수는 2와 다른 소수 홀수의 합으로 이루어진다. 

따라서 홀수-2가 소수인지만 판별하면 된다.

 

3) 소수인지 판별은 앞서 말했듯 에라토스테네스의 체 범위보다 크면 소수로 나눈다. 나누어지면 소수가 아니다.

그 범위보다 작으면 바로 에라토스테네스의 체로 구해놓은 소수배열에서 꺼내쓴다.