[Python] 백준 - 9020 - 골드바흐의 추측

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

T = int(input())

for i in range(T):
    n = int(input())
    sosu_list = []
    answer = [None, None]

    for i in range(n-1, 2, -1):
        chk = 0

        for k in range(2, i): 
            if i % k == 0: # i가 소수아님
                chk += 1
                break
        if chk == 0:
            # i가 소수임
            sosu_list.append(i)


    sosu_list.append(2)

    for i in range(0, len(sosu_list)//2):
        for k in range(-1, -(len(sosu_list)//2+2), -1):
            if sosu_list[i] + sosu_list[k] == n:
                answer[0] = sosu_list[i]
                answer[1] = sosu_list[k]
                break

    print(min(answer), max(answer))

3
8
3 5
10
5 5
16
5 11

꾸역꾸역했더니 시간초과..

# 9020

sosu_list = [False, False] + [True] * 10000
    
for i in range(2, 101):
    if sosu_list[i] == True: # i(2~100) 가 True(소수o)이면
        for j in range(2*i, 10001, i): 
        	# i의 배수들을 False(소수x)로 변경 ex) i = 3 -> 6, 9, 12, 15, ... / i = 4 -> 8, 12, 16, 20, ...
            sosu_list[j] = False
        # 이러면 소수만 True로 남게 됨

T = int(input())
for t in range(T):
    n = int(input())
    answer = [n//2, n//2]
    
    for i in range(n//2):
        if sosu_list[answer[0]] == True and sosu_list[answer[1]] == True and sum(answer) == n:
            print(answer[0], answer[1])
            break
        answer[0] = answer[0] - 1
        answer[1] = answer[1] + 1

3
8
3 5
10
5 5
16
5 11

https://yoonsang-it.tistory.com/31
소수 리스트 만드는 알고리즘 참고해서 완성!

시간복잡도를 줄이기 위해 앞 숫자를 고정하고 뒤 숫자를 반복하면서 탐색하는 것을 중간부터 양쪽으로 더하고 빼면서 탐색하는 것으로 변경함
(for문 하나를 없앰)