익숙해지기 참 어려운 소수

#6588 골드바흐의 추측 https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

정말 피곤한 문제였다.

 

소수는 에라토스테네스의 체를 이용해서 구해야한다. 이건 매번 이해만 하고 외워지지가 않는다. 멍청한걸까?

bool_prime = [False, False] + [True]*(1000000-1)
prime = []
for i in range(2, 1000000 + 1):
    if bool_prime[i]:
        prime.append(i)
        for j in range(2*i, 1000000 + 1, i):
            bool_prime[j] = False

이번 문제에서는 자꾸 시간초과가 나서 어려웠는데 총 두가지 이슈가 있었다.

 

[ 첫 번째 이슈 ] : in 사용하기

for n in prime:
	if num - n in prime:
		answer = [n, num-n]
		break

파이썬에서 in은 참 편리하다. 하지만 in은 루프를 돌린다. (굉장히 무식한 탐색이랄까? 하지만 가장 정확하지)

때문에 in 문장 하나에서 O(n)의 시간이 발생한다. 그걸 두번을 했으니 시간초과가 나지.

 

엥? 근데 바꿔도 시간초과가 또 나네? 뭐지?

 

[ 두 번째 이슈 ] : 데이터

while True:
    num = int(input())
    half = num//2
    if num == 0:
        break
    else:
        bool_prime = [False, False] + [True]*(num-1)
        prime = []
        for i in range(2, half+1):
            if bool_prime[i]:
                prime.append(i)
                for j in range(2*i, half+1, i):
                    bool_prime[j] = False

이 문제는 소수판별을 매 입력값 마다 진행해줘야하는데, while문 안에 소수생성기능을 하는 코드를 넣어놔서 시간초과가 난 것이었다. while문 밖에서 필요한 최대 크기의 소수생성을 해 놓은 뒤 while내에서는 입력과 판별 후 출력을 반복하면 된다. 어휴 멍청해서....

 

[ 그렇게 나온 정답 ]

bool_prime = [False, False] + [True]*(1000000-1)
prime = []
for i in range(2, 1000000 + 1):
    if bool_prime[i]:
        prime.append(i)
        for j in range(2*i, 1000000 + 1, i):
            bool_prime[j] = False
while True:
    num = int(input())
    if num == 0:
        break
    else:
        answer = 0
        for n in prime:
            if bool_prime[num - n]:
                print("{} = {} + {}".format(num, n, num-n))
                answer += 1
                break
        if answer == 0:
            print("Goldbach's conjecture is wrong.")

깔끔하게 정답!