9020_골드바흐의추측

🗨️ Comment

• 매번 특정 수보다 작은 소수 목록을 뽑는 것은 비효율적이다 → 범위안의 가능한 모든 소수 목록을 만들어두고, 그 중에서 차자
  
• n을 이루는 소수의 조합 찾기
  • 처음에는 조합을 떠올렸지만, 나오는 소수리스트 길이를 생각하면 시간초과가 발생하고 비효율적
  • 소수 리스트중 두개의 수를 뽑고, 더해서 n을 만들어야한다 → 뽑는 기준에 대소관계를 이용할 수 있다
    
  • 선형탐색에서 시간을 줄이는 방법 → 이분탐색을 떠올리기
• 하나의 수를 두번 선택할 수 있음 , 두 소수의 차이를 최소로 해야한다 → s, e모두 나란히 +1씩 한다 → 더 커졌을 경우, s부터 뒤로가기
  

풀기 전 주석메모

# 2초 / 256MB
# 23.05.18
# 15:33 ~ 15: 45 / 16:00 ~ 16:41 / 
# 소수 / 5 -> 1, 5
# 골드바흐수 정의 
    # 2보다 큰 모든 짝수 <- 두 소수의 합
# 골드바흐 파티션

# 10,000보다 작은 모든 소수를 미리 수집? 
    #     2, 3, 5, 7, /  11, 13, 17,/  23, 29, / 31, 37, / 41, 43, 47, ..  ... 

  # 8 <- 8보다 작은 두개의 소수로 이루어짐
  # 10 <- 10보다 작은 두개의 소수로 ... 
  # 일단 1~10,000까지 순회하면서 소수리스트 생성하기

# 리스트에서, 8의 후보가 될 수 있는 범위 좁히기.. 
    #     이진탐색 -> if 8이 더 크면, 종료 
    #     거기서 2개 뽑기? 

    # output: 골드바흐 파티션 출력
    # a, b 두개 출력 / 작은것부터 출력

정답코드

import sys
input = sys.stdin.readline

T = int(input()) #

def check(num):
    for i in range(2, num//2 + 1):  # num//2까지 검사
        if num % i == 0:
            return False
    return True

_list = []
for i in range(2, 10001):
    # 소수 판정
    if check(i):
        _list.append(i)

for t in range(T):
    n = int(input()) # 2보다 큰 짝수 / 

    s = 0
    e = 0
    for i in range(len(_list)):
        if _list[s] + _list[e] == n:
            print(_list[s], _list[e])
            break 
        elif _list[s] + _list[e] < n:
            s += 1
            e += 1
        else:
            s -= 1