BOJ 15711: 환상의 짝꿍 [Python 3]

문제가 단순히 소수를 판단하는 문제인 줄 알았는데, 극악의 정답률을 자랑하는 데에는 이유가 있다.

 

---

t=int(input())
data=[]
for _ in range(t):
    data.append(list(map(int,input().split())))
num=0
primes=[]
for i in data:
    num=max(sum(i),num)
a=[False,False]+[True]*(num-1)
for i in range(2,int(num**0.5)+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i,num+1,i):
            a[j]=False
for i in range(len(a)):
    if a[i]:
        primes.append(i)
for i in data:
    limit=sum(i)
    flag=0
    for j in range(2,limit//2+1):
        if j in primes and limit-j in primes:
            flag=1
            print("YES")
            break
    if not flag:
        print("NO")

처음에 내가 풀려고 했던 코드이다.

단순히 에라토스테네스의 체 알고리즘을 이용해서 해결하려고 했으나, 문제는 해당 리스트의 크기가 2의 12제곱이 된다.

메모리 초과가 발생하게 된다.

 

그렇기 때문에 새로 고안한 코드이다.

n=2*(10**6)
a=[False,False]+[True]*(n-1)
for i in range(2,int(n**0.5)+1):
    if a[i]:
        for j in range(2*i,n+1,i):
            a[j]=False
prime=[i for i in range(2,n) if a[i]]
for _ in range(int(input())):
    a,b=map(int,input().split())
    if a+b<4:
        print("NO")
    elif not (a+b)%2:
        print("YES")
    else:
        if a+b-2>=n:
            flag=0
            for p in prime:
                if not (a+b-2)%p:
                    flag=1
                    print("NO")
                    break
            if not flag:
                print("YES")
        else:
            if a+b-2 in prime:
                print("YES")
            else:
                print("NO")

먼저 리스트의 크기를 2 곱하기 10의 6제곱으로 줄였다.

최대 4 곱하기 10의 제곱의 크기의 정수를 소수 판별 할 때 2부터 2 곱하기 10의 6제곱의 사이에 있는 소수만 나눠보면 되기 때문이다.

 

그래서 똑같이 에라토스테네스의 체 알고리즘을 이용하여 소수 리스트를 정하고, 

수들을 input 받는다.

이 때, 4보다 작은 자연수는 무조건 나눌 수 없기에 NO를 출력해주고,

짝수는 골드바흐의 추측 때문에 무조건 YES이다.

 

https://acupoframen.tistory.com/18

BOJ 6588: 골드바흐의 추측

https://namu.wiki/w/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%20%EC%B6%94%EC%B8%A1

골드바흐 추측 - 나무위키

골드바흐의 추측에 의거해 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있기에, 해당 경우는 이렇게 처리해줬다.

 

만약 두 수의 합이 리스트의 크기보다 큰 홀수가 N이라고 가정하자.

모든 소수는 2를 제외하고 다 홀수이고,

홀수 더하기 홀수는 짝수이기 때문에,

N은 2와 N-2의 소수로 이루어져야 한다.

그렇기에 N-2가 소수임을 증명하면 된다.

 

N-2가 리스트보다 작은 수이면, 소수 리스트에 N-2가 있는지 확인해주면 쉽게 확인 가능하다.

 

N-2가 리스트보다 큰 수이면, 소수 리스트에 있는 수들로 나누어보고, 나누어 떨어지면 합성수, 나누어 떨어지지 않으면 소수이다.

 

 

---

쉬우면서도 복잡한 소수 판별 문제였다.