S2 9020. 골드바흐의 추측

문제 보기 :  9020번: 골드바흐의 추측

---

문제

• 정답률 : 39%

 

---

작성 코드

T = int(input())

# 에라토스테네스의 체를 사용해 소수 판별 리스트 생성
max_m = 10000 # 소수 계산의 최대값
ari_map = [False,False]+[True]*(max_m-1)
for i in range(2,max_m+1):
    if ari_map[i]:
        for j in range(2*i,max_m+1,i):
            ari_map[j]=False

for _ in range(T):
    n = int(input())

    # n을 두 소수의 합으로 표현하기 위한 초기 값 설정
    left = n//2 # 중간값부터 시작 (작은 소수)
    right = n//2 # 중간값부터 시작 (큰 소수)

    # left와 right가 모두 소수일 때까지 반복
    while not ari_map[left] or not ari_map[right]:
        left -= 1 ; right += 1

    print(left, right)

---

풀이

이 코드는 입력받은 짝수를 두 소수의 합으로 표현하는 문제를 해결하는 프로그램이다.

먼저, 에라토스테네스의 체를 사용해 10,000 이하의 소수를 미리 계산한다.

소수를 저장하는 리스트 ari_map을 생성하고, 소수가 아닌 수는 False로 설정한다. 테스트 케이스마다 입력받은 짝수 n을 두 소수의 합으로 표현하기 위해 left와 right를 n // 2로 초기화한다.

이는 두 소수의 차이가 가장 적은 경우를 먼저 탐색하기 위함이다. left와 right 중 하나라도 소수가 아니라면, left를 줄이고 right를 늘려 조건에 맞는 두 소수를 찾는다. 찾은 두 소수 left와 right를 출력하며, 이 과정은 입력된 테스트 케이스 수만큼 반복된다.

프로그램은 소수를 미리 계산하여 효율적으로 동작하며, 입력된 짝수는 항상 소수의 합으로 표현 가능하다는 전제 조건을 활용한다.