BOJ #9020 골드바흐의 추측

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 9020. 골드바흐의 추측

문제 풀이

입력값의 범위가 정해져 있으므로 전체 값에 대해 소수를 모두 판별해둔다. 그리고 짝수가 입력되므로 절반으로 나누어 중앙값에서부터 양쪽을 1씩 더하고 빼면서 둘 다 소수인 경우를 처음으로 만족할 때 출력 후 종료하면 해당 값들이 가장 차이가 작은 경우에 해당한다.

python 코드

import sys

N = 10000 # 최대 입력 값
sieve = [True for _ in range(N)] # 에라토스테네스 체 준비
sieve[0] = False # 1은 소수가 아님
for i in range(2, int(N ** 0.5) + 1): # 2부터 제곱근까지
    for j in range(2 * i, N, i): # i는 제외, 2i부터 i간격으로
        if sieve[j-1]: # 좌표값은 -1해서 처리(1번째는 0번 좌표)
            sieve[j-1] = False
case = int(input())

for _ in range(case): # 각 케이스에 대해
    n = int(sys.stdin.readline())
    k = n // 2 # 입력값이 짝수이므로 중앙에서 시작
    for i in range(k - 1): # 0부터 k-2까지
        if sieve[k - i - 1] and sieve[k + i - 1]: # 모두 소수?
            print(f"{k-i} {k+i}") # 출력
            break # 종료