[Python] 백준(BOJ) 15711번: 환상의 짝꿍

문제

15711번: 환상의 짝꿍

풀이

파이썬으로 제출한 사람들은 다 밀러-라빈 소수판별법을 사용했지만 나는 다른 방법으로 풀고싶어서 고집을 부리다가..

결국 시간초과가 나서 pypy3로 제출한 문제.

 

 

두 끈의 합 s가  

2 or 3일 경우 -> NO

4 이상의 짝수인 경우 -> YES

 

그리고 그 외에는 홀수인 경우만 남는다. 

홀수는 홀수+짝수로밖에 이루어질 수 없고, 짝수인 소수는 2밖에 없기 때문에

홀수가 두 소수의 합이 되려면 2 + 홀수소수 인 경우밖에 없다. 

 

따라서 s-2가 소수인지 확인해주면 된다.

문제는, 맥스값이 너무 커서 그냥 확인해주면 안된다.

애초에 에리스토스테네스의 체로 소수를 다 구해놓고 시작하는데, 맥스값인 2*10^12로하면 터진다.

따라서 2*10^6의 값까지 구해놓고 s-2가 이 값보다 클 경우, 소수로 나눠지는지 확인, 

이 값보다 작을경우 에리스토스테네스의 체에서 구한 배열에서 바로 확인해주면 된다. 

 

이 문제에서 신기했던 값이 워낙 크다보니

1. 0~2000000까지 모든 수를 다 훑으며 소수인지 아닌지 확인하고, 소수인 애들을 따로 배열에 저장하기

그 후 for prime in primes 이런식으로 소수 꺼내쓰기

 

2. 0~sqrt(2000000)까지만 확인하고 배열의 불린값으로 소수인지 아닌지 저장하기

그 후 0~2000000까지 돌면서 배열의 불린값으로 소수인지 아닌지 확인하기

 

리스트에서 in을 쓰는게 O(N)이라 1번이 더 오래걸릴줄 알았는데, 써놓고보니 2번이 말이안되게 느린게 보인다.

두 방법중 1번이 거의 반정도의 시간으로 더 빨랐다.

 

import sys

# 문제의 맥스값까지의 소수를 미리 다 구하기 (값이 커서 소수들을 따로 저장해둠)
num = 2000000
arr = [False, False] + [True for _ in range(num-1)]
primes = []
for i in range(2, num+1):
    if arr[i]:
        primes.append(i)
        for k in range(i+i, num, i):
            arr[k] = False


def isPrime(n):
	# 2000000보다 크면 소수로 나눠지는지 확인
    if n > num:
        for prime in primes:
            if prime >= n:
                break
            elif n % prime == 0:
                return False
        return True
        
    # 2000000보다 작으면 소수인지 바로 확인
    else:
        return arr[n]


T = int(sys.stdin.readline())

for _ in range(T):
    A, B = map(int, sys.stdin.readline().split(" "))
    s = A+B

    # 2나 3일 경우엔 NO
    if s < 4:
        print("NO")

    # 합이 4 이상의 짝수일 경우는 무조건 YES (-> 골드바흐의 추측)
    elif s % 2 == 0:
        print("YES")

    # 홀수소수는 짝수소수(2)+홀수소수의 조합으로밖에 안됨
    # s-2가 소수인지 확인
    else:
        if isPrime(s-2):
            print("YES")
        else:
            print("NO")